Determinarea maximumului unei funcții polinomiale arbitrare

In general, orice sarcina abstracta care trebuie indeplinita, poate fi privita ca fiind rezolvarea unei probleme, care, la randul ei, poate fi perceputa ca o cautare in spatiul solutiilor potentiale.

Deoarece, de obicei, cautam cea mai buna solutie, putem privi acest proces ca fiind unul de optimizare. Pentru spatii mici, metodele clasice exhaustive sunt suficiente; pentru spatii mari, pot fi folosite tehnicile speciale ale inteligentei artificiale.

Metodele calculului evolutiv se numara printre aceste tehnici; ele folosesc algoritmi ale caror metode de cautare au ca model cateva fenomene naturale: mostenirea genetica si lupta pentru supravietuire. Cele mai cunoscute tehnici din clasa calculului evolutiv sunt algoritmii genetici, strategiile evolutive, programarea genetica si programarea evolutiva. Exista si alte sisteme hibride care incorporeaza diferite proprietati ale paradigmelor de mai sus; mai mult, structura oricarui algoritm de calcul evolutiv este, in mare masura, aceeasi.

In ultimii 30 de ani, s-a manifestat un mare interes in rezolvarea problemelor de sistem bazate pe principiile evolutiei si ereditatii. Astfel de sisteme mentin o populatie de solutii potentiale, ele au unele procese de selectie bazate pe fitness individual, si cativa operatori genetici. Un astfel de sistem este o clasa a evolutiei strategice i.e, algoritmi care imita principiile evolutiei naturale pentru problemele de optimizare de parametru (Rechemberg, Schwefel). Evolutia programarii lui Fogel este o

tehnica de cautare intr-un spatiu finit, mic de masini. Tehnologiile de cautare a masinii lui Glover Scatter mentin o populatie de puncte de referinta, generand o stare speciala prin greutatea combinatiilor liniare.

Alte tipuri de sisteme evolutionare sunt Holland.s Genetic Algorithms. In 1990 Koza a propus un astfel de sistem evolutional, genetic programming, pentru a cauta cel mai potrivit program de computer sa rezolve o problema particulara. Folosind un termen comun E.P pentru toate sistemele (incluzand sistemele descrise mai sus). Structura evolutiei programului este :

Inceputurile algoritmilor genetici se situeaza undeva in jurul anului 1950, cand mai multi biologi au folosit calculatoarele pentru simularea sistemelor biologice. Rezultatele muncii au inceput sa apara dupa 1960, cand la Universitatea din Michigan, sub directa indrumare a lui John Holland, algoritmii genetici au aparut in forma in care sunt cunoscuti astazi.

Dupa cum sugereaza si numele, algoritmii genetici folosesc principii din genetica naturala. Cateva principii fundamentale ale geneticii sunt imprumutate si folosite artificial pentru a construi algoritmi de cautare care sunt robusti si cer informatii minime despre problema.

1. Genetic Algorithms + Data Structures = Evolution Programs, Zbigniew Michalewicsz, Second, Extended Edition

2. Beasley D., Bull D.R., Martin R.R., An Overview of Genetic Algorithms, Part 1, Foundations, University Computing, Vol.15, No.4, pp. 170-181, 1993;

3. Dumitrescu D., Algoritmi genetici si strategii evolutive -

Aplicatii in inteligenta artificiala si in domenii conexe, Editura Albastra, Cluj-Napoca, 2000;

4. Goldberg D.E., Genetic Algorithms in Search,

Optimization and Machine Learning, Addison - Wesley, Reading, MA,1989;

5. Garey M.R., Johnson D.S., Computers and Intractability:

A Guide to NP-completeness, W.H. Freeman and Company, New York, 1978.

6. Koza J.R., Genetic Programming, MIT Press, Cambridge, MA, 1992;

7. Oltean M., Proiectarea si implementarea algoritmilor, Computer Libris Agora, Cluj-Napoca, 2000.