To tylko jedna z 4 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Inteligencja Obliczeniowa
Sprawozdanie nr 6
Student: Katarzyna Nidecka
Kierunek: Informatyka i ekonometria
Rok: 3
Grupa laboratoryjna: 3
Naszym zadaniem podczas tych laboratoriów było znalezienie ekstremum funkcji:
f(x) = x*sin(10*π*x)+1 na przedziale [-1, 2] za pomocą metod heurystycznych. Na początku posługujemy się algorytmem losowego przeszukiwania na reprezentacji binarnej. Piszemy program, do którego z początku wprowadzamy długość łańcucha bitów, który decyduje o długości tablicy. Następnie tablica losowa jest wypełniana wartością 0 lub 1, natomiast te są konwertowane na liczby rzeczywiste. Następnie wyliczamy wartość funkcji f(x) za argumenty przyjmując przekonwertowane liczby. Szukamy maksimum. Gdy jest większe od poprzedniego, program go zapamiętuje. Dochodzi do mutacji losowej liczby (bez względy na to czy maksimum było większe od poprzedniego czy nie).
Algorytm pełnego przeglądu wartości na liczbach rzeczywistych. Program sprawdza z dokładnością 0,001 kolejne liczby rzeczywiste z danego przedziału. Następnie oblicza wartość funkcji i porównuje ją z wartością funkcji liczby poprzedniej. Jeśli nowa wartość funkcji jest wyższa od poprzedniej zostaje ona zapamiętana. Tym sposobem algorytm poszukuje maksimum, które pod koniec programu zostaje wypisane na ekran. Algorytm ten jest łatwy w implementacji, jednak jest on nieefektywny. Pełny przegląd wartości jest czasochłonny (w naszym przypadku czas znalezienia maksimum jest krótki, jednak przedział przeszukiwań jest stosunkowo wąski).
Następnie posługujemy się algorytmem Tabu Search. Algorytm na każdym stopniu iteracji przeszukuje sąsiedztwo w celu wyboru najlepszego rozwiązania, które staje się bazowym w następnym kroku. Ostatni wykonany ruch trafia na listę zabronionych ruchów i nie może być wykonany przez określoną liczbę iteracji. Algorytm ten umożliwia wyjście z lokalnego minimum i zapobiega przed cyklicznością ruchów. Wykonanie ruchu zabronionego jest możliwe w przypadku określenia przez funkcję aspiracji zyskowności tego ruchu. Koniec obliczeń następuje po wykonaniu maksymalnej liczby iteracji. for (i = 1; i fmax) {
xmax = x; fmax = fx;
}
Na końcu działaliśmy na klasycznym algorytmie genetycznym, który jest najbardziej rozbudowaną heurystyką na jakiej pracowaliśmy. Program inicjalizuje populację początkową o danym rozmiarze i długości genotypu. Wartości kolejnych genotypów są wybierane losowo. Chromosomy zapisane zostają na liście. Następuje ewaluacja stworzonej populacji. Wyliczana jest wartość dziesiętna chromosomów oraz odpowiadająca im wartość funkcji . Później następuje szukanie najlepszego chromosomu i zapamiętanie go.
... zobacz całą notatkę
Komentarze użytkowników (0)