NATURAL SOLVERS IN PROBLEMS OF SEARCHING FOR THE BEST SOLUTION

Anna Jasinska-Suwada, Witold Dzwinel, Krzysztof Rozmus, Jacek Soltysiak

Abstract


In the paper we present a new method, which can be used as a natural solver for searching the best solution in the multidimensional and multimodal parameter space. The method is based on

a well-known simulation techniąue, i.e., molecular dynamics. To show advantages and disadvanta- ges of the particie method in comparison to the standard genetic algorithm, we analyse efficiency of the methods in finding the global minimum of multi-dimensional and multi-modal test-bed functions and we calculate the evaluation indices. We analyse also the ways the solution space is explored and the parameters of algorithms adjusted. The optimal heuristics are proposed. The tests carried out show that the choice of the most appriopriate optimization method depends on type of a problem considered. We show that the particie method is morę efficient for finding the optimal solution for multi-modal problems with distinct global extreme, while the genetic algo­ rithm is better for deceptive functions with several locals extreme, which are placed far away from the global optimum. This comes from the different ways in which the particie method and genetic algorithm explore the solution space. The particie method can be used for initial analysis of functions, which character is unknown.


Full Text:

PDF

References


Krawczyk S.: Programowanie matematyczne. Warszawa, PWE 1980

Goldberg D.E.: Algorytmy genetyczne i ich zastosowania, tłum. z j. ang. Warszawa, WNT 1995

Battiti R., Tecchiolli G.: Simulated Annealing and Tabu Search in the Long Run: a Comparison on QAP Tasks. Computers and Mathematics with Applications, 1994, 28(6)

Ingber L.: Simulated annealing: Practice versus theory. J. Math. Comput. Modelling,

, 18(11), 29

Dzwinel W.: Informatyczne problemy i perspektywy symulacji metodą cząstek. Ze szyty Naukowe AGH, Rozprawy i monografie, 50, 1996

Dzwinel W.: Yirtual particles and search for global minimum. Futurę Generation Computer Systems, 12, 1997

Tadeusiewicz R.: Sieci neuronowe. Warszawa, Akademicka Oficyna Wydawnicza RM 1993

Hertz J., Krogh A., Palmer R.G.: Wstęp do teorii obliczeń neuronowych, tłum. z j. ang., Warszawa, WNT 1993

Dorigo M., Maniezzo V., Colomi A.: The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybemetics-Part B, 26, No. 1, 1996

Battiti R., Tecchiolli G.: Local Search with Memory: Benchmarking RTS. Operations Reserch Spectrum 1995

Sloot P.M.A., Kaandorp J.A, Schoneveld A.: Dynamie Complex System (DCS): a new approach to parallel computing in computional physics. Technical Report, Universi- ty of Amsterdam, grudzień 1995

Mahfoud S.W., Goldberg D.E.: Parallel recombinative simulated annealing: A genetic algorithm. Parallel Computing, 21, 1995

Kirkpatrick S., Gellat C.D., Vecchi M.P.: Optimization by Simulated Annealing. Science, 220,1984

Dueck G., Scheuer T.: Threshold Accepting.A General Purpose Optimization Algo rithm Appearing Superior to Simulated Annealing. Jumal of Comput. Phys., 90, 1,

Ingber L.: Adaptive Simulated Annealing (ASA): Lessons Lerned. Control and Cyber-

netics, 1995

Andricioaei I.A., Straub J.E.: Finding the Needle in the Haystack: Algorithms for

Conformational Optimization. Computers in Physics, 10, Sep/Oct 1996

Spears W.M.: An overview of evolutionary computation. European Conference of

Machinę Leaming, 1993

Harik G., Cantu-Paz E., Goldberg D., Miller B.L.: The Gambler’s

Ruin Problem, Ge

netic Algoritmand the Sizing ofPopulation, IlliGAL web page

Potter M.A.,De Jong K.A.: A cooperative Coevolutionary Approach to Function Op

timization. The Third Parallel Problem Solving From Naturę, Jerusalem, 1994

Rozmus K., Sołtysiak J.: Wposzukiwaniu minimum globalnego. Praca magisterska (AGH, Wydział Elektrotechniki, Automatyki Informatyki i Elektroniki), Kraków,

czerwiec 1998

Łaguza M.: Problemy GA-trudne. Praca magisterska (AGH, Wydział Elektrotechniki,

Automatyki Informatyki i Elektroniki), Kraków, wrzesień 1998

Goldberg D.E., Deb K., Horn J.: Massive Multimodality, Deception and Genetic Al-

goritms. IlliGAL Report No. 92005, kwiecień 1992

Horn J., Goldberg D.E., Deb K.: Long Path Problem. The Third Conference on Pa

rallel Problem Solving from Naturę, Jerusalem, październik 1994

Price K., Storm R.: Ewolucja ró nicowa. Software, czerwiec 1997

Strona WWW http://solon.cma.univie.ac.at/~neum

Strona WWW http://gal4.ge.uiuc.edu/cei-bin/orderform/

Strona WWW http://cs.und.ae.za/-~ikram/Research/

Strona WWW htto://www.wins.unva.nl/research/qwrs/introalg.html

Strona WWW http://iridia.ulb.ac.be/Langerman/ICEO.html

Strona WWW http://www.es.umass.edu/mie/

Strona WWW http://www.abafi/~atorn/Globopt.html

Broda A.: Relacje przestrzenne i lokalność interakcji pomiędzy osobnikami populacji

w algorytmach genetycznych. Praca magisterska (AGH, Wydział Elektrotechniki,

Automatyki Informatyki i Elektroniki), Kraków, wrzesień 1996

Zieliński K. i inni: Środowiska programowania rozproszonego w sieciach komputerowych. Kraków 1994

Campanini R., Di Caro G., Villani M., D’Antone I., Giusti G.: Parallel architectures and intrinsically parallel algorithms: genetic algorithms. International Journal of Modem Physics C, 5, 11, 1994

http://www.aic.nrl.naw.mil/galist/

http://gal4.ge.uiuc.edu/goldberg/d-goldberg.html/

http://www-iligal.ge.uiuc.edu/%7Ebmiller

Goldberg D.E.: The design of innovation: lessonsfrom genetic algoritms, lessonsfor

the real world. IlliGAL Report No. 98004, luty 1998

Cantu-Paz E.: A summary o f research on parallel genetic algorithms. IlliGAL Report

No. 95007, 1995

http://www.aic.nrl.naw.mil/galist/src/

http://alumni .caltech.edu/~in gber/

http://www.ingber.com/ASA README.html

http://www.wins.uva.nl/research/pwrs/proiects/DvnCompSvs.html

Fox G.C.: Parallel Computers and Complex Systems. Complexity International, 1,

kwiecień 1994; dostępne przez: http://www.csu.edu.au/ci/voll/Geoffrev.Fox/

Findeisen W., Szymanowski J., Wierzbicki A.: Metody obliczeniowe optymalizacji.

Warszawa, Wydawnictwa Politechniki Warszawskiej 1973

Gajęcki M.: Algorytm rozwiązujący problem komiwoja era i jego implementacja na

ró nych architekturach. Praca doktorska (AGH, Wydział Elektrotechniki, Automaty ki, Informatyki i Elektroniki), Kraków, 1996




DOI: https://doi.org/10.7494/csci.2000.2.0.3578

Refbacks

  • There are currently no refbacks.