Autor: Zbigniew Michalewicz, David B. Fogel

ISBN: 83-204-3108-5

Ilość stron: 626

Data wydania: 05/2006

Twarda oprawa

Książka "Jak to rozwiązać czyli nowoczesna heurystyka" dotyczy rozwiązywania skomplikowanych problemów o dużej złożoności obliczeniowej. Autorzy określają źródła trudności, przed którymi staje każdy rozwiązujący skomplikowane zadanie. Przedstawiają klasyczne algorytmy optymalizacyjne. Omawiają dwie współczesne heurystyki: symulowane wyżarzanie i wyszukiwanie z tabu. Opisują zagadnienia związane z poszukiwaniem permutacji obiektów spełniających zadane warunki i dostrajaniem algorytmów do naszych potrzeb.

Zajmują się sieciami neuronowymi, systemami rozmytymi i metodami hybrydowymi. Bardzo ważne są dodatki. W pierwszym autorzy podają podstawowe wiadomości z rachunku prawdopodobieństwa i statystyki, potrzebne do zrozumienia książki, a w drugim zamieszczają problemy do samodzielnego przestudiowania.

Książka jest przeznaczona dla studentów informatyki, nauk przyrodniczych i zarządzania na uczelniach wyższych.

Rozdziały:

I.         Ile lat mają moi trzej synowie?

1.            Dlaczego niektóre problemy są trudne do rozwiązania?
1.1.          Wielkość przestrzeni przeszukiwania
1.2.          Modelowanie problemu
1.3.          Zmiana związana z czasem
1.4.          Ograniczenia
1.5.          Problemy z udowadnianiem
1.6.          Twoja szansa na sławę
1.7.          Podsumowanie

II.        Jak ważny jest model?

2.            Podstawowe pojęcia
2.1.          Reprezentacja
2.2.          Cel
2.3.          Funkcja oceny
2.4.          Określanie problemu poszukiwania
2.5.          Otoczenia i lokalne optima
2.6.          Metody wspinania się
2.7.          Czy umiesz tak sprytnie uderzyć bilę?
2.8.          Podsumowanie

III.      Jakie są ceny w sklepach „7-11"?

3.            Metody tradycyjne - część I
3.1.          Przeszukiwanie wyczerpujące
3.1.1.       Metody wyliczeniowe dla SAT
3.1.2.       Metody wyliczeniowe dla TSP
3.1.3.       Metody wyliczeniowe dla NLP
3.2.          Przeszukiwanie lokalne
3.2.1.       Przeszukiwanie lokalne i SAT
3.2.2.       Przeszukiwanie lokalne i TSP
3.2.3.       Przeszukiwanie lokalne i NLP
3.3.          Programowanie liniowe: metoda sympleks
3.4.          Podsumowanie

IV.       Jakie to liczby?

4.            Metody tradycyjne - część II
4.1.          Algorytmy zachłanne
4.1.1.       Algorytmy zachłanne i SAT
4.1.2.       Algorytmy zachłanne i TSP
4.1.3.       Algorytmy zachłanne i NLP
4.2.          Dziel i rządź
4.3.          Programowanie dynamiczne
4.4.          Metoda podziału i ograniczeń
4.5.          Algorytm A*
4.6.          Podsumowanie

V.        Jakiego koloru jest niedźwiedź?

5.            Unikanie lokalnych optimów
5.1.          Symulowane wyżarzanie
5.2.          Poszukiwanie z tabu
5.3.          Podsumowanie

VI.       Jak dobrą masz intuicję?

6.            Podejście ewolucyjne
6.1.          Podejście ewolucyjne do SAT
6.2.          Podejście ewolucyjne do TSP
6.3.          Podejście ewolucyjne do NLP
6.4.          Podsumowanie

VII.     Jedna z tych rzeczy jest niepodobna do pozostałych

7.            Projektowanie algorytmów ewolucyjnych
7.1.          Reprezentacja
7.1.1.       Wektory symboli o ustalonej długości
7.1.2.       Permutacje
7.1.3.       Automaty ze skończoną liczbą stanów
7.1.4.       Wyrażenia symboliczne
7.2.          Funkcja oceny
7.3.          Operatory różnicowania
7.3.1.       Wektory symboli o ustalonej długości
7.3.2.       Permutacje
7.3.3.       Automaty ze skończoną liczbą stanów
7.3.4.       Wyrażenia symboliczne
7.4.          Selekcja
7.5.          Inicjowanie
7.6.          Podsumowanie

VIII.    Jaka jest najkrótsza droga?

8.            Problem komiwojażera
8.1.          W poszukiwaniu dobrych operatorów różnicowania
8.2.          Uzupełnianie o metody poszukiwania lokalnego
8.3.          Inne możliwości
8.3.1.       Krzyżowanie ze składaniem krawędzi
8.3.2.       Operator inver-over
8.4.          Podsumowanie

IX.       Kto ma zebrę?

9.            Metody radzenia sobie z ograniczeniami
9.1.          Ogólne rozważania
9.1.1.       Określanie funkcji evalf
9.1.2.       Określanie funkcji evalu
9.1.3.       Zależności między evalf a evalu
9.1.4.       Odrzucanie rozwiązań niedopuszczalnych
9.1.5.       Poprawianie osobników niedopuszczalnych
9.1.6.       Zastępowanie osobników ich poprawionymi wersjami
9.1.7.       Nakładanie kar na osobniki niedopuszczalne
9.1.8.       Utrzymywanie populacji dopuszczalnej za pomocą specjalnych sposobów reprezentacji i
                operatorów różnicowania
9.1.9.       Stosowanie dekoderów
9.1.10.     Oddzielanie osobników i ograniczeń
9.1.11.     Badanie granicy między dopuszczalną a niedopuszczalną częścią przestrzeni
                przeszukiwania
9.1.12.     Znajdowanie rozwiązań dopuszczalnych
9.2.          Optymalizacja numeryczna
9.2.1.       Metody oparte na zachowywaniu dopuszczalności rozwiązań
9.2.2.       Metody oparte na funkcjach kary
9.2.3.       Metody oparte na poszukiwaniu rozwiązań dopuszczalnych
9.2.4.       Metody oparte na dekoderach
9.2.5.       Metody hybrydowe
9.3.          Podsumowanie

X.        Czy potrafisz dostosować się do problemu?

10.          Dostosowywanie algorytmu do problemu
10.1.        Parametry sterujące w algorytmach ewolucyjnych
10.2.        Objaśnienie zagadnienia za pomocą NLP
10.3.        Taksonomia metod sterowania
10.4.        Możliwości sterowania parametrami
10.4.1.     Reprezentacja
10.4.2.     Funkcja oceny
10.4.3.     Operatory mutacji i ich prawdopodobieństwa
10.4.4.     Operatory krzyżowania i ich prawdopodobieństwa
10.4.5.     Selekcja rodziców
10.4.6.     Populacja
10.5.        Łączenie sposobów sterowania parametrami
10.6.        Podsumowanie

XI.       Czy potrafisz dać mata w dwóch ruchach?

11.          Środowiska zmienne w czasie oraz szum
11.1.        Życie to dynamiczny krajobraz
11.2.        Świat rzeczywisty jest zaszumiony
11.2.1.     Zapewnianie różnorodności
11.3.        Modelowanie trasy statku
11.4.        Podsumowanie

XII.     Dzień tygodnia, w którym wypada pierwszy stycznia

12.          Sieci neuronowe
12.1.        Neurony progowe i liniowe funkcje dyskryminacyjne
12.2.        Propagacja wsteczna dla wielowarstwowych perceptronów ze sprzężeniem do przodu
12.3.        Szkolenie i testowanie
12.4.        Sieci rekurencyjne i architektury rozszerzone
12.4.1.     Standardowe sieci rekurencyjne
12.4.2.     Sieć Hopfielda
12.4.3.     Maszyna Boltzmanna
12.4.4.     Sieć wielu współpracujących programów
12.5.        Grupowanie za pomocą uczenia konkurencyjnego
12.6.        Wykorzystywanie sieci neuronowych do rozwiązywania TSP
12.7.        Ewoluujące sieci neuronowe
12.8.        Podsumowanie

XIII.    Jakiej długości była lina?

13.          Systemy rozmyte
13.1.        Zbiory rozmyte
13.2.        Zbiory rozmyte i miary probabilistyczne
13.3.        Operacje na zbiorach rozmytych
13.4.        Relacje rozmyte
13.5.        Projektowanie regulatora rozmytego
13.6.        Grupowanie rozmyte
13.7.        Rozmyte sieci neuronowe
13.8.        Podejście rozmyte do TSP
13.9.        Ewoluujące systemy rozmyte
13.10.      Podsumowanie

XIV.    Wszystko od czegoś zależy

14.          Systemy koewolucyjne
14.1.        Gry
14.2.        Uczymy się grać w warcaby
14.3.        Optymalizacja z użyciem konkurujących populacji
14.4.        Jeszcze jeden przykład gry
14.5.        Sztuczne życie
14.6.        Gry ze współpracą i konkurowaniem
14.7.        Modelowanie inteligentnych agentów
14.8.        Zagadnienia związane z koewolucją
14.9.        Przykład koewolucji ze współpracą w zastosowaniu do TSP
14.10.      Podsumowanie

XV.      Kto jest wyższy?

15.          Wielokryterialne podejmowanie decyzji
15.1.        Redukowanie do problemów z jedną liczbą
15.1.1.     Valuated State Space
15.1.2.     Metody rozmyte wielokryterialnego podejmowania decyzji
15.1.3.     Podsumowanie
15.2.        Podejście ewolucyjne do wielokryterialnego podejmowania decyzji
15.2.1.     Krótka historia
15.2.2.     Algorytm ewolucyjny dla wielokryterialnego NLP
15.3.        Podsumowanie

XVI.    Czy lubisz proste rozwiązania?

16.          Systemy hybrydowe
16.1.        Podsumowanie

17.          Podsumowanie

Dodatek A.           Rachunek prawdopodobieństwa i statystyka
A.1.        Podstawowe pojęcia rachunku prawdopodobieństwa
A.2.        Zmienne losowe
A.2.1.     Dyskretne zmienne losowe
A.2.2.     Ciągłe zmienne losowe
A.3.        Statystyki opisowe zmiennych losowych
A.4.        Twierdzenia graniczne i nierówności rachunku prawdopodobieństwa
A.5.        Dodawanie zmiennych losowych
A.6.        Generowanie liczb losowych przez komputer
A.7.        Szacowanie
A.8.        Statystyczne testowanie hipotez
A.9.        Regresja liniowa
A.10.      Podsumowanie

Dodatek B.           Zadania i projekty
B.l.          Kilka praktycznych problemów
B.2.         Ogłaszanie wyników eksperymentów obliczeniowych z zastosowaniem metod heurystycznych