Fejlett keresőalgoritmusok

Aszalós, László

Bakó, Mária

DEIK
Debreceni Egyetem
Informatikai Kar


            Debrecen
            4032
            Egyetem tér 1
          

A tananyag a TÁMOP-4.1.2.A/1-11/1-2011-0103 azonosítójú pályázat keretében valósulhatott meg.

2012


Tartalom

Előszó
1. Bevezetés
2. Adatszerkezetek
Jelölések
State osztály
StateR osztály
StateRC osztály
Keresztezés
Közelítés
SolvingMethod osztály
Feladatok
3. Lokális keresések
Hegymászó algoritmus
HillClimbingTools segédosztály
Hagyományos algoritmus
Hagyományos algoritmus randomizált variánsa
Hagyományos algoritmus szűkített variánsa
Iterált hegymászó algoritmus
Absztrakt módszer iterált keresésre
Iterált módszer - teljes környezet
Iterált módszer - véletlen szomszédok
Iterált módszer - szűkített környezetek
Szétszórt keresés
Absztrak módszer szétszórt keresésre
Szétszórt keresés - teljes környezet
Szétszór keresés - véletlen szomszédok
Szétszórt keresés - szűkített környezetek
Tabu keresés
Tabu keresés - közös rutinok
Tabulista
Lépés kiválasztása
Lépések rövid távú memóriával
Absztrak módszer rövid távú memóriával
Tabu keresés - teljes környezet
Tabu módszer - véletlen szomszédok
Tabu keresés - szűkített környezetek
Tabu keresés középtávú memóriával
Középtávú memória használata
Absztrakt módszer középtávú memóriával
Középtávú memória - teljes környezet
Középtávú memória - véletlen szomszédok
Középtávú memória - szűkített környezetek
Feladatok
Sztochasztikus hegymászó algoritmus
Akkumulált javítások
Sztochasztikus keresés implementációja
Feladatok
Szimulált hűtés
Szimulált hűtés implementációja
Párhuzamos hűtés
Konfliktusok módszerei
Minimális konfliktusok
Max-min konfliktusok
Jó elem kiválasztása
Segédosztály konfliktusok kezelésére
Javított módszer
Jó elem megválasztása
Javított segédosztály
Feladatok
4. Sokaságokon alapuló algoritmusok
Evolúciós stratégia
Evolúció - absztrakt módszer
Segédosztály evolúcióhoz
(μ,λ) változat
(μ+λ) változat
Speciális evolúció változat
Feladatok
Genetikus algoritmus
Absztrakt genetikus algoritmus
Elitista megközelítés
Konkrét megvalósítások
Stabil megközelítés
Üresedés
Konkrét megvalósítások
Feladatok
Rovarraj implementáció
Belső osztály rovaroknak
Rovar osztály alkalmazása
Feladatok
Szentjánosbogár algoritmus
Háttér
Szentjánosbogár algoritmus megvalósítása
Feladatok
Méhek algoritmusa
Háttér
Méhek algoritmusának implementációja
Apróbb változtatás a követő méheknél
Méhek változó környezet variánsa
Feladatok
Harmónia keresés
Háttér
Harmónia keresés implementációja
Feladatok
Kereszt-entrópia
Kereszt-entrópia implementációja
Feladatok
5. Konkrét feladat: korrelációs klaszterezés
Cluster osztály
Gráf ábrázolása
Jelölt gráf ábrázolása mátrixszal
Egészek mátrixa
Bitek mátrixai
Feladatok
Gráf generálása
Mátrixsorozat generálása
Erdős-Rényi gráfgenerálás
Mátrixsorozat mentése
Barabási-Albert modell
Feladatok
Csoportosítás megadása
Klaszterek megadása
Számsorozat ábrázolás
Bitmátrixos ábrázolás
Kombinált ábrázolás
Futási eredmények kiírása
Eredmények kiírása
Célfüggvény értéke
Leíró statisztika
Segédosztályok
BitMatrix
Bitvektor
Solution
Main osztály
Konstansok
6. Speciális keresési módszerek
Összevonás mint keresési módszer
Összevonás segédosztálya
Összevonások módszere
Összevonás variáns segédosztálya
Összevonás variáns
Kombinált módszerek
Minimális konfliktusok és összevonás
Max-min konfliktusok és összevonás
Max-min variáns és összevonás
Feladatok
7. Futási eredmények
Hegymászó keresések
alap módszer és variánsai
Iterált hegymászó
Szétszórt keresés
Sztochasztikus hegymászó
Tabu keresés
Szimulált hűtés
Konfliktusok
Evolúciós stratégia, genetikus algoritmus
Rovarok
Harmónia keresés
Kereszt-entrópia
Kontrakció
Hibrid módszerek
Összegzés
Feladatok
8. Kényszer-kielégítés
Elméleti alapok
Feladatok
9. Feladatok
Kombinatorikus optimalizálás
Átfogó problémák
Bibliográfia

Az ábrák listája

2.1. Egy pont és környezete
2.2. Egy pont és szűkített környezetei
2.3. State és bővítéseinek osztálydiagramja
2.4. Absztrakt megoldást kereső algoritmus
3.1. Hegymászó keresés és variánsainak osztálydiagramja
3.2. Iterált hegymászó keresés és variánsainak osztálydiagramja
3.3. Szétszórt keresés és variánsainak osztálydiagramja
3.4. Tabu keresés, azok variánsaink és segédosztályainak áttekintő ábrája
3.5. Általános tabu keresés absztrakt osztálya
3.6. Segédosztályok a lépés kiválasztására
3.7. Rövidtávú memóriát felhasználó keresések osztályai
3.8. Segédosztályok a lépés kiválasztására
3.9. Sztochasztikus keresés lépéseihez tartozó differenciák és az azok alapján generált függvény.
3.10. Véletlen r érték, és a hozzá tartozó y lépés kiválasztása
3.11. A sztochasztikus hegymászó kereséshez kapcsolódó osztályok osztálydiagramja
3.12. A szimulált hűtéshez kapcsolódó osztályok osztálydiagramja
3.13. Konfliktusok módszereinek osztálydiagramja
4.1. Evolúciós algoritmus osztálydiagramja
4.2. Genetikus módszerek áttekintő osztálydiagramja
4.3. Genetikus algoritmusok közös része
4.4. Elitista genetikus algoritmusok osztálydiagramja
4.5. Stabil genetikus algoritmusok osztálydiagramja
4.6. Rovarraj módszer osztálydiagramja
4.7. Firefly osztály
4.8. Bees osztály
4.9. Bee2 osztály
4.10. HarmonySearch osztály
4.11. CrossEntropy osztály
5.1. Cluster osztály
5.2. Cluster osztály kapcsolata más osztályokkal
5.3. Mátrix tárolására használt osztályok
5.4. Gráf generálására használt osztályok
5.5. A partíciót ábrázoló szám n-es és bitmátrixos megfelelője
5.6. Groups osztálydiagram
5.7. PrintSolution osztálydiagram
5.8. Bitek tárolására használt osztályok
5.9. Tesztek futtatását intéző osztályok
6.1. Összevonás módszereinek osztálydiagramja
6.2. Kombinált összevonások osztálydiagramjai
7.1. Hegymászó keresés és First Better variánsának célfüggvényértékei
7.2. Hegymászó keresés és First Better variánsának maximális klaszterméretei
7.3. Hegymászó keresés és irányok szűkítése
7.4. Hegymászó keresés és variánsai
7.5. Hegymászó keresés és iterált hegymászó keresés (teljes környezet) összehasonlítása
7.6. Az iterált a hagyományos hegymászó keresés célfüggvényértékeinek aránya
7.7. A mutáció foka megválasztásának következményei
7.8. Iterált hegymászó keresés és variánsai
7.9. A hagyományos, az iterált és a szétszórt hegymászó keresés célfüggvényértékeinek aránya
7.10. Szétszórt hegymászó keresés és variánsai
7.11. A hagyományos és sztochasztikus hegymászó módszerek
7.12. Sztochasztikus és hagyományos hegymászó keresés aránya
7.13. Különféle tabu keresések összehasonlítása
7.14. Tabu keresés célfüggvényértékeinek aránya a hegymászó kereséshez viszonyítva
7.15. Tabu keresés és hegymászó keresés célfüggvényértékeinek aránya
7.16. Tabu lista hosszának hatása a célfüggvényértékekre
7.17. Lépésszám hatása a célfüggvényértékére
7.18. Szimulált és párhuzamos hűtés különböző lépésszámokkal
7.19. Min. illetve max-min konfliktusok és variánsa
7.20. Különféle evolúciós stratégiák két lépésszám esetén
7.21. Elitista genetikus algoritmusok
7.22. Stabil genetikus algoritmusok
7.23. Rovarraj optimalizáció
7.24. Szentjánosbogár algoritmus
7.25. Méhek algoritmusa
7.26. Harmónia keresés
7.27. Kereszt-entrópia módszere
7.28. Sokaságokon alapuló módszerek
7.29. Összevonás módszere és variánsa
7.30. Kontrakció és min. valamint max-min konfliktusok
7.31. Célfüggvényértékek arányai hibrid módszerek esetén
7.32. Módszerek eredményeinek összehasonlítása
7.33. A legjobban teljesítő módszerek
7.34. Futási idők összehasonlítása

A táblázatok listája

5.1. Bell számok