Normaalijakaumaan perustuva mutaatio-operaatio differentiaalievoluutioalgoritmiin

Evoluutioalgoritmit ovat viime vuosina osoittautuneet tehokkaiksi menetelmiksi globaalien optimointitehtävien ratkaisuun. Niiden vahvuutena on etenkin yleiskäyttöisyys ja kyky löytää globaali ratkaisu juuttumatta optimoitavan tavoitefunktion paikallisiin optimikohtiin. Tässä työssä on tavoitteena kehittää uusi, normaalijakaumaan perustuva mutaatio-operaatio differentiaalievoluutioalgoritmiin, joka on eräs uusimmista evoluutiopohjaisista optimointialgoritmeista. Menetelmän oletetaan vähentävän entisestään sekä populaation ennenaikaisen suppenemisen, että algoritmin tilojen juuttumisen riskiä ja se on teoreettisesti osoitettavissa suppenevaksi. Tämä ei päde alkuperäisen differentiaalievoluution tapauksessa, koska on voitu osoittaa, että sen tilanmuutokset voivat pienellä todennäköisyydellä juuttua. Työssä uuden menetelmän toimintaa tarkastellaan kokeellisesti käyttäen testiongelmina monirajoiteongelmia. Rajoitefunktioiden käsittelyyn käytetään Jouni Lampisen kehittämää, Pareto-optimaalisuuden periaatteeseen perustuvaa menetelmää. Samalla saadaan kerättyä lisää kokeellista näyttöä myös tämän menetelmän toiminnasta. Kaikki käytetyt testiongelmat kyettiin ratkaisemaan sekä alkuperäisellä differentiaalievoluutiolla, että uutta mutaatio-operaatiota käyttävällä versiolla. Uusi menetelmä osoittautui kuitenkin luotettavammaksi sellaisissa tapauksissa, joissa alkuperäisellä algoritmilla oli vaikeuksia. Lisäksi useimmat ongelmat kyettiin ratkaisemaan luotettavasti pienemmällä populaation koolla kuin alkuperäistä differentiaalievoluutiota käytettäessä. Uuden menetelmän käyttö myös mahdollistaa paremmin sellaisten kontrolliparametrien käytön, joilla hausta saadaan rotaatioinvariantti. Laskennallisesti uusi menetelmä on hieman alkuperäistä differentiaalievoluutiota raskaampi ja se tarvitsee yhden kontrolliparametrin enemmän. Uusille kontrolliparametreille määritettiin kuitenkin mahdollisimman yleiskäyttöiset arvot, joita käyttämällä on mahdollista ratkaista suuri joukko erilaisia ongelmia.

In recent years evolutionary algorithms have proven to be effective methods for solving global optimization problems. Their strength lies especially in generality and ability to avoid getting stuck in local optima. The goal of this thesis is to develop a new gaussian probability distribution based mutation operation for Differential Evolution algorithm. Differential Evolution is one of the most recent novel evolutionary algorithms. It is expected that this new method reduces the risk of premature convergence and stagnation. Additionally it can be proven convergent theoretically. For the original differential evolution algorithm it can be shown that there is always a small probability for stagnation and thus it is not provably convergent. In this thesis multi-constrained problems are used as test problems for the algorithm. The method used for handling constraints is based on Pareto optimality and it is developed by Jouni Lampinen. One goal is also to gather more practical evidence about this method. Both the original Differential Evolution algorithm and the version with new mutation operation were able to solve all used test problems. However, the new method showed better robustness in cases, where the original algorithm had problems. Additionally most of the tested problems could be solved using smaller population size with the new method reliably. Another advantage of the new method is that it better enables the use of control parameters that lead to a rotationally invariant algorithm. The new method is computationally somewhat more expensive in comparison with the original Differential Evolution. It also requires one control parameter more. In this thesis, however, widely applicable values for the new control parameters were empirically determined. These were selected so that as wide range of different problems as possible could be solved using these values.