Nieformalnie algorytm to zestaw krok\u00f3w, kt\u00f3re nale\u017cy wykona\u0107, aby zrealizowa\u0107 pewne zadanie. Aby komputer m\u00f3g\u0142 wykona\u0107 jakie\u015b zadanie, nale\u017cy najpierw opracowa\u0107 algorytm opisuj\u0105cy spos\u00f3b wykonania tego zadania i przedstawi\u0107 go w postaci zrozumia\u0142ej dla komputera (w postaci programu). Jedna z formalnych definicji algorytmu jest nast\u0119puj\u0105ca: \u201ealgorytm jest uporz\u0105dkowanym zbiorem jednoznacznych, wykonywalnych krok\u00f3w, okre\u015blaj\u0105cym sko\u0144czony proces\u201d[1]<\/a>. Istniej\u0105 tak\u017ce inne pr\u00f3by okre\u015blenia tego, czym s\u0105 algorytmy, kt\u00f3re uwypuklaj\u0105 m.in. mo\u017cliwo\u015b\u0107 ich implementowania na klasycznych komputerach cyfrowych. Tego rodzaju algorytmami niew\u0105tpliwie s\u0105 algorytmy ewolucyjne.<\/p>\n Algorytmy ewolucyjne to jeden z kilku podstawowych nurt\u00f3w rozwojowych w informatyce czerpi\u0105cych inspiracje z ustale\u0144 biologii ewolucyjnej. Okre\u015blane s\u0105 one zbiorcz\u0105 nazw\u0105 algorytm\u00f3w ewolucyjnych a nale\u017c\u0105 do nich: programowanie ewolucyjne, strategie ewolucyjne, algorytmy genetyczne oraz genetyczne programowanie[2]<\/a>.<\/p>\n Istnieje wiele sposob\u00f3w recepcji algorytm\u00f3w ewolucyjnych. Mo\u017cna widzie\u0107 w nich metody sztucznej inteligencji, modele ewolucji i genetyki (tzw. sztuczne \u017cycie) lub pr\u00f3by rozwi\u0105zania zadania optymalizacji globalnej[3]<\/a>. Najog\u00f3lniej rzecz ujmuj\u0105c algorytm ewolucyjny realizuje proces ci\u0105g\u0142ej adaptacji symulowanej populacji do zadanego wirtualnego \u015brodowiska. Ograniczeniem tej metody symulacji jest to, \u017ce nie mo\u017cna zagwarantowa\u0107, i\u017c wynikiem tego procesu obliczeniowego b\u0119dzie znalezienie najlepszego osobnika z teoretycznie mo\u017cliwych. Jednak\u017ce wraz z up\u0142ywem czasu dzia\u0142ania takiego algorytmu prawdopodobie\u0144stwo takiego wyniku wzrasta i d\u0105\u017cy asymptotycznie do jedno\u015bci[4]<\/a>.<\/p>\n Dowolny algorytm ewolucyjny przetwarza populacj\u0119 osobnik\u00f3w a ka\u017cdy z nich jest jak\u0105\u015b propozycj\u0105 rozwi\u0105zania postawionego wcze\u015bniej oraz jednoznacznie zdefiniowanego problemu badawczego[5]<\/a>. Dzia\u0142a on w wirtualnym \u015brodowisku, kt\u00f3re zdefiniowane jest na podstawie postawionego problemu badawczego, kt\u00f3ry pr\u00f3buje si\u0119 rozwi\u0105za\u0107 z u\u017cyciem tego algorytmu. W tym cyfrowym \u015brodowisku ka\u017cdemu wirtualnemu osobnikowi przyporz\u0105dkowana jest warto\u015b\u0107 liczbowa, kt\u00f3ra okre\u015bla jako\u015b\u0107 reprezentowanego przez niego rozwi\u0105zania. Warto\u015b\u0107 t\u0119 najcz\u0119\u015bciej nazywa si\u0119 przystosowaniem konkretnego osobnika do danego wirtualnego \u015brodowiska.<\/p>\n Standardowe dzia\u0142anie algorytmu ewolucyjnego polega na wykonywaniu p\u0119tli, w kt\u00f3rej nast\u0119puj\u0105 po sobie nast\u0119puj\u0105ce procedury: reprodukcja (preselekcja), operacje genetyczne, ocena i sukcesja (postselekcja); czasami reprodukcj\u0119 i sukcesj\u0119 nazywa si\u0119 zbiorczo selekcj\u0105. Zanim tak opisana p\u0119tla wirtualnej ewolucji b\u0119dzie mog\u0142a zadzia\u0142a\u0107, potrzebna jest faza wst\u0119pnej inicjacji, kt\u00f3ra polega na utworzeniu pocz\u0105tkowej cyfrowej populacji bazowej poprzez losowe wygenerowanie genotyp\u00f3w osobnik\u00f3w i obliczenie ich przystosowania.<\/p>\n Tak zarysowana cyfrowa ewolucja mo\u017ce zosta\u0107 zako\u0144czona, gdy przystosowanie osobnik\u00f3w jest odpowiednio du\u017ce (tj. zgodne z za\u0142o\u017conym uprzednio przez osob\u0119 inicjuj\u0105c\u0105 t\u0119 symulacj\u0119), gdy stwierdzi si\u0119, \u017ce populacja bazowa uleg\u0142a stagnacji (tj. w kolejnych cyklach nie poprawia si\u0119 przystosowanie osobnik\u00f3w) lub gdy algorytm ewolucyjny przeszed\u0142 konkretn\u0105 liczb\u0119 iteracji (cykli), kt\u00f3re by\u0142y wcze\u015bniej okre\u015blone.<\/p>\n Przedstawiony wy\u017cej og\u00f3lny spos\u00f3b dzia\u0142ania algorytm\u00f3w ewolucyjnych nale\u017ca\u0142oby dookre\u015bli\u0107 i uzupe\u0142ni\u0107 o istotne szczeg\u00f3\u0142y z uwagi na to, o czym wspomniano ju\u017c wcze\u015bniej, \u017ce algorytmy te dziel\u0105 si\u0119 na cztery podstawowe typy: algorytmy genetyczne, strategie ewolucyjne, programowanie ewolucyjne oraz programowanie genetyczne.<\/p>\n Niezale\u017cnie od tego, kt\u00f3r\u0105 wersj\u0119 algorytmu ewolucyjnego b\u0119dziemy rozpatrywa\u0107 pojawia si\u0119 problem jego algorytmiczno\u015bci. Czy tego typu procesy obliczeniowe, z uwagi na inspiracje zwi\u0105zane z biologi\u0105 ewolucyjn\u0105, mo\u017cna analizowa\u0107 z perspektywy klasycznej algorytmiki? Czy procesy ewolucyjne, zaimplementowane w strukturze algorytm\u00f3w ewolucyjnych, s\u0105 algorytmizowalne? Czy zatem standardowe okre\u015blenia tego, czym w swej istocie s\u0105 algorytmy, s\u0105 nadal adekwatne w kontek\u015bcie algorytm\u00f3w ewolucyjnych? Czy nie nale\u017ca\u0142oby zaproponowa\u0107 jakiej\u015b innej ich charakterystyki? Nasz referat po\u015bwi\u0119cony b\u0119dzie zarysowaniu wst\u0119pnych odpowiedzi na powy\u017csze pytania oraz ustaleniom potrzebnych kontekst\u00f3w, aby odpowiedzi te mog\u0142y sta\u0107 si\u0119 bardziej precyzyjne.<\/p>\n Algorytmy ewolucyjne s\u0105 bowiem implementowane na klasycznych komputerach cyfrowych, co niew\u0105tpliwie \u015bwiadczy o ich algorytmiczno\u015bci. Z drugiej jednak strony, nale\u017c\u0105 do klasy indeterministycznych metod heurystycznych inspirowanych biologicznie, co mo\u017ce czyni\u0107 je niezgodnymi z klasyczn\u0105 definicj\u0105 algorytmu.<\/p>\n [1]<\/a> J.G. Brookshear, Informatyka w og\u00f3lnym zarysie<\/em>, Wydawnictwa Naukowo-Techniczne, Warszawa 2003, s. 181<\/p>\n [2]<\/a> Por. J. Arabas, Wyk\u0142ady z algorytm\u00f3w ewolucyjnych<\/em>, Warszawa: Wydawnictwo Naukowo-Techniczne 2004, s.\u00a017-19.<\/p>\n [3]<\/a> Por. J. Arabas, dz. cyt., s. 21.<\/p>\n [4]<\/a> Por. tam\u017ce, s. 20.<\/p>\n [5]<\/a> Dzia\u0142anie algorytm\u00f3w ewolucyjnych omawiam na podstawie dost\u0119pnej literatury przedmiotu, tj. mi\u0119dzy innymi: J. Arabas, dz. cyt., s. 15-17; M. Flasi\u0144ski, Wst\u0119p do sztucznej inteligencji, <\/em>Warszawa: Wydawnictwo Naukowe PWN 2011, s. 58-72; L. Rutkowski, Metody i techniki sztucznej inteligencji<\/em>, Warszawa: Wydawnictwo Naukowe PWN 2011, s. 237-307.<\/p>\n","protected":false},"excerpt":{"rendered":" Nieformalnie algorytm to zestaw krok\u00f3w, kt\u00f3re nale\u017cy wykona\u0107, aby zrealizowa\u0107 pewne zadanie. Aby komputer m\u00f3g\u0142 wykona\u0107 jakie\u015b zadanie, nale\u017cy najpierw opracowa\u0107 algorytm opisuj\u0105cy spos\u00f3b wykonania tego zadania i przedstawi\u0107 go w postaci zrozumia\u0142ej dla komputera (w postaci programu). Jedna z … Czytaj dalej