Improving evolutionary algorithms for multi-objective optimisation: Generating high trade-off solutions and introducing a novel stopping criterion

Viviane De Buck
Dit werk focust op de verbetering van evolutionaire computeralgoritmen die gebruikt worden voor de optimalisatie van (bio-)chemische processen. De hoofdbijdrage van dit werk is enerzijds de introductie van gebruikersvoorkeuren in de optimalisatieprocedure en anderzijds de ontwikkeling van een nieuw, probleem-relevant stopcriterium voor het algoritme. Dit geeft aanleiding tot een vereenvoudigd keuzeproces en een kortere rekentijd.

Het (explosieve) dilemma van duurzame chemie

Exploderende olieraffinaderij

De vraag “Wat gaan we eten?” is misschien wel de moeilijkste vraag van het hele universum. De onvermijdelijke besluiteloosheid die erop volgt, heeft al menige relaties het vuur aan de schenen gelegd. Hou je het deze avond simpel, wil je uitgebreid koken, of ga je uit eten? Een keuze moet je in ieder geval maken, maar het dagelijkse dilemma is onvermijdbaar want meerdere keuzes lijken even aantrekkelijk. Alleen heb jij één voordeel: jouw uiteindelijke beslissing kan hoogstens aanleiding geven tot een smaakexplosie, maar niet meer dan dat. Dergelijke dilemma’s zijn evenwel niet beperkt tot enkel beslissen wat er ’s avonds gegeten zal worden, maar komen in alle vormen en formaten voor. De inzet van dergelijke vragen kan in al die gevallen bovendien beduidende verschillen vertonen. Zo kunnen de dilemma’s waarmee de chemische industrie geconfronteerd wordt, leiden tot soms zeer explosieve uitkomsten, zij het ongewenst.

Big people, big planet en big profit

De chemische industrie wordt vaak gezien als een raszuivere big profit industrie. In een wereld vol aluminium constructies en kilometerslange pijpleidingen, lijkt er niet veel plaats te zijn voor de planeet en de mensen die erop leven. Toch wordt de chemische industrie steeds meer geconfronteerd met de omliggende wereld. Zo dwingt klimaatverandering de industrie om rekening te houden met het milieu, terwijl een duurzame bedrijfsvoering enkel kan verwezenlijkt worden indien er ook ingezet wordt op de omliggende samenleving en de mensen die in de industrie werkzaam zijn. Winst maken is dus lang niet meer het enige argument in de chemische bedrijfsvoering, en dit brengt problemen met zich mee.

Veilig, goedkoop, én duurzaam?

Laten we even teruggrijpen naar het dilemma van het avondeten. Voedsel dat simultaan veilig, goedkoop, en op een duurzame manier verbouwd en verwerkt is, lijkt een utopie. Voor duurzaam en veilig voedsel moet je over het algemeen als eens dieper in de buidel tasten, terwijl van goedkoop voedsel niet veel duurzaamheid verwacht wordt. En hoewel het voor zoiets alledaags als voedsel reeds onmogelijk lijkt om de drie vernoemde criteria te vervullen, moet de complexe chemische nijverheid hier wel kunnen aan voldoen.

Chemische processen optimaliseren zodat ze simultaan veilig, goedkoop, en duurzaam worden, is echter een moeilijke opgave. Aangezien er naast pure procesmatige doelstellingen ook aan sociale, milieu-, en economische doelstellingen moet voldaan worden, neemt de omvang van het optimalisatieprobleem enkel maar toe. Daarenboven hebben deze doelstellingen vaak tegenstrijdige optimale waarden. Zo kan men zich makkelijk inbeelden dat indien enkel economische doelstellingen in beschouwing genomen worden, het resulterende chemische proces niet noemenswaardig milieuvriendelijk zal zijn. In het geval van dergelijke optimalisatieproblemen, waarbij er aan verschillende tegenstrijdige doelstellingen tegelijkertijd moet voldaan worden, is er dus geen unieke optimale oplossing voorhanden. Integendeel, voor deze optimalisatieproblemen bestaan er theoretisch gezien oneindig veel evenwaardige optimale oplossingen waartussen een afweging moet gemaakt worden door de ingenieurs en procesontwerpers.

Darwin was een computergenie

Aangezien chemische processen zeer complex zijn, wordt er bij de optimalisatie ervan gebruik gemaakt van wiskundige benaderingsmodellen. De vooropgestelde optimalisatiedoelstellingen worden tevens vertaald in wiskundige vergelijkingen, waardoor het volledige optimalisatieprobleem getransformeerd wordt in een wiskundig probleem. De optimalisatie is nu dus vertaald naar het vinden van optimale oplossingen waarvan de integrale (productie-)kost het laagst is.

Om proces- en ontwerpingenieurs een handje te helpen, werden voor zulke optimalisatieproblemen specifieke computeralgoritmen ontwikkeld die al het rekenwerk op zich nemen. Een populaire groep van zulke algoritmen zijn evolutionaire algoritmen die gebruik maken van de mechanismen voorgesteld in de evolutietheorie van Darwin. Daar waar de informatie van levende organismen opgeslagen is in de genen van het DNA, kan de informatie van optimale oplossingen ook zo opgevat worden: elke vooropgestelde doelstelling stelt één gen voor in het DNA van de oplossingen. Door de genen van oplossingen te combineren (zoals tijdens seksuele voortplanting bij levende organismen), en ze te muteren, worden er nieuwe oplossingen gevormd. Door vervolgens het principe van natuurlijke selectie toe te passen en telkens enkel de beste oplossingen te selecteren, bereiken de oplossingen uiteindelijk hun meest optimale waarden. Dit proces wordt herhaald tot wanneer er geen verschil meer merkbaar is tussen twee opeenvolgende generaties van oplossingen, en de meest optimale oplossingen dus bereikt zijn. Merk op dat er in de natuur steeds ruimte is voor verdere optimalisaties en veranderingen maar dat de oplossingen van de optimalisatieproblemen vaak begrensd worden door de limitaties van, bijvoorbeeld, de gebruikte apparatuur, en deze dus convergeren naar optimale waarden.

Te veel informatie leidt tot geen informatie

Het grootste probleem van dergelijke evolutionaire computeralgoritmen is dat ze heel veel informatie generen over het optimalisatieprobleem. Zoals reeds vermeld, zijn er voor dergelijke optimalisatieproblemen in theorie oneindig veel oplossingen. Wanneer een chemisch bedrijf een procesoptimalisatie doorvoert, kan het echter maar uiteindelijk één oplossing toepassen op het werkelijke proces. Het kiezen van één oplossing uit een enorm grote groep evenwaardige oplossingen leidt dus tot dilemma’s. Voor dit probleem werden twee oplossingen ontwikkeld. In eerste instantie werden de computeralgoritmen voorzien van de mogelijkheid om de voorkeuren van de ingenieurs en ontwerpers in rekening te brengen, waardoor de gegeneerde informatie bijna gedecimeerd wordt. Sommige gegenereerde oplossingen voldoen namelijk niet aan de vooropgestelde voorkeuren, en worden door de ontwikkelde filter niet meer weergegeven in de uiteindelijke oplossingsverzameling. Hierdoor wordt het keuzeproces significant vereenvoudigd. De voorkeuren van de ingenieurs en ontwerpers worden bovendien gebruikt om na te gaan wanneer het algoritme kan stoppen met het genereren van oplossingen. Als de gegenereerde oplossingen niet langer voldoen aan de vooropgestelde voorkeuren, is het nutteloos om verder oplossingen te generen. Deze tweede aanpassing leidt vooral tot een significante tijdswinst tijdens het optimalisatieproces, en time is money.

Het uiteindelijke ontworpen evolutionaire computeralgoritme stelt ingenieurs en ontwerpers dus in staat de nodige optimalisaties van chemische processen te berekenen in een minimale tijd, waarbij rekening gehouden wordt met gebruikersvoorkeuren om het keuzeproces te vereenvoudigen. Deze aanpak toont bovendien ook veel potentieel om toegepast te worden voor optimalisatieprocedures in andere industriële sectoren (zoals de logistiek). Of het algoritme jou kan helpen met de moeilijkste vraag van het universum, moet echter nog verder onderzocht worden.

Bibliografie

H. Asefi, F. Jolai, M. Rabiee, and M.E. Tayebi Araghi. A hybrid nsga-ii and vns for solving a bi-objective no-wait flexible flowshop scheduling problem. International Journal of Advanced Manufacturing Technology, 75:1017–1033, 2014.

T. Back. Evolutionary algorithms in theory and practice: Evolution strategies, evolutionary programming, genetic algorithms. Oxford University Press, 198 Madison Avenue, New York, New York 10016, 1996.

J. Branke, K. Deb, H. Dierolf, and M. Osswald. Finding knees in multi-objective optimization. In Parallel Problem Solving from Nature - PPSN-VIII, pages 722–731, 2004.

CEFIC. Landscape of the european chemical industry 2017, belgium. Online, 2017. URL https://www.chemlandscape.cefic.org/country/belgium/.

I. Das and J.E. Dennis. A closer look at drawbacks of minimizing weighted sums of objectives for pareto set generation in multi-criteria optimization problems. Structural Optimization, 14, 1997.

I. Das and J.E. Dennis. Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 8, 1998.

K. Deb and H. Jain. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. Evolutionary Computation, IEEE Transactions on, 18(4):577–601, 2014.

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. Evolutionary Computation, IEEE Transactions on, 6(2):182–197, 2002.

K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable Test Problems for Evolutionary Multiobjective Optimization, pages 105–145. Springer London, London, 2005.

I. Hashem, D. Telen, P. Nimmegeers, F. Logist, and J. Van Impe. A novel algorithm for fast representation of a pareto front with adaptive resolution: Application to multi-objective optimisation of a chemical reactor. Computers and Chemical Engineering, 106, 2017.

H. Jain and K. Deb. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part II: Handling constraints and extending to an adaptive approach. Evolutionary Computation, IEEE Transactions on, 18(4):602–622, 2014.

S.M. Kalami. NSGA-II in MATLAB. Online, 2015. URL http://yarpiz.com/56/ypea120-nsga2.

S.M. Kalami. NSGA-III: Non-dominated sorting genetic algorithm, the third version. Online, 2016. URL http://yarpiz.com/456/ypea126-nsga3.

K. Liagkouras and K. Metaxiotis. Enhancing the performance of moeas: an experimental presentation of a new fitness guided mutation operator. Journal of Experimental and Theoretical Artificial Intelligence, 29(1):91–131, 2017.

F. Logist, B. Houska, M. Diehl, and J. Van Impe. Fast pareto set generation for nonlinear optimal control problems with multiple objectives. Structural and Multidisciplinary Optimization, 42:591–603, 2010.

C.A. Mattson, A.A. Mullur, and A. Messac. Smart pareto filter: obtaining a minimal representation of multiobjective design space. Engineering Optimization, 36(6):721–740, 2004.

A. Messac, A. Ismail-Yahaya, and C.A. Mattson. The normalized normal constraint method for generating the pareto frontier. Structural and Multidisciplinary Optimization, 25, 2003.

C.A. Munoz Lopez, D. Telen, P. Nimmegeers, L. Cabianca, F. Logist, and J. Van Impe. A process simulator interface for multiobjective optimization of chemical processes. Computers and Chemical Engineering, 109:119–137, 2018.

M. Rabiee, M. Zandieh, and P. Ramezani. Bi-objective partial flexible job shop scheduling problem: NSGAII, NRGA, MOGA and PAES approaches. International Journal of Production Research, 50(24):7327–7342, 2012.

M. Tanaka, H. Watanabe, Y. Furukawa, and T. Tanino. Ga-based decision support system for multicriteria optimization. 1995 IEEE International Conference on Systems, Man and Cybernetics. Intelligent Systems for the 21st Century, 5:1556–1561, 1995.

J. Valadi and P. Siarry, editors. Applications of Metaheuristics in Process Engineering. Springer International Publishing Switzerland, 2014.

M. Vallerio, D. Vercammen, J. Van Impe, and F. Logist. Interactive NBI and (E)NNC methods for the progressive exploration of the criteria space in multi-objective optimization and optimal control. Computers and Chemical Engineering, 82, 2015.

Y. Yuan, H. Xu, and B. Wang. An improved NSGA-III procedure for evolutionary many-objective optimization. In GECCO’14 Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pages 661–668, 2014.

Universiteit of Hogeschool
Master in de industriële wetenschappen: biochemie
Publicatiejaar
2018
Promotor(en)
Prof. Jan Van Impe
Kernwoorden
Share this on: