Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
10
Rozdział1.Wprowadzenie
Analizująctrajektorięprzeszukiwaniaprzestrzenirozwiązańnaturalnejestreprezen-
towanietegoprocesujakoprzeszukiwaniegrafu(sąsiedztwa),wktórymodwiedzanesą
wierzchołki.Współczesnemetaheurystykiprzeglądająrzędu109takichwierzchołków,
wkażdymznichwyznaczająclubszacującwartośćfunkcjikryterialnej.Ogromnaliczba
badanychrozwiązańoznaczarównieżgenerowanieiprzetwarzanieogromnychporcjida-
nych(np.dlaproblemugniazdowegoz200operacjamijestto12,27TB/godz.).Jednak
podczasdziałaniawiększościobecnychalgorytmów,decyzjedotyczącekierunkudal-
szychposzukiwańpodejmowanesanapodstawiebieżącegostanulubkrótkiejhistorii
obejmującejniewielkąliczbęwykonanychjużiteracjialgorytmu.
Problememwkonstrukcjachefektywnychalgorytmówjestnietylkoliczbabadanych
rozwiązań.ZtwierdzenianofreelunchWolpert’aiMacready’egowynika,żebezwbu-
dowaniawalgorytmspecyficznychwłasnościrozwiązywanegoproblemunieotrzymamy
algorytmugeneralnielepszegoodinnych.Koniecznesąwięcwszechstronnebadaniapro-
blemóworazprzestrzenirozwiązańposzczególnychinstancjiprowadzącedoskrócenia
czasuobliczeńorazpoprawieniawartościwyznaczanychrozwiązań.Zdotychczasowych
doświadczeńwynika,żekonstruowanieakceptowalnychwpraktycealgorytmówwymaga
indywidualnegopodejściadokażdegozagadnieniaijestzazwyczajoddzielnymproble-
membadawczym,któremupoświęcasięczęstowielepublikacji.
Monografiadotyczybadańprzestrzenirozwiązańproblemówoptymalizacjidyskretnej
podkątemspecyficznychwłasności,któremożnazastosowaćwkonstrukcjachefektyw-
nychalgorytmów.Obejmujezagadnieniazarównointeresująceteoretycznie,jakiważne
praktycznie.Sątobowiemnietylkotradycyjneproblemywynikającezkomputerowego
wspomaganiasystemówwytwarzaniaorazzarządzania,aletakżezupełnienowe,często
znaczniebardziejzłożone,związanezintensywnierozwijającąsiętelekomunikacją,tele-
transmisją,atakżedystrybucjątowaróworazusług.Bardzodużyrozmiarpraktycznych
przykładóworazwykładniczorosnącyczasobliczeń(algorytmówdokładnych)powodują,
żedorozwiązywaniarozpatrywanychproblemówstosowanesąniemalwyłączniemetody
przybliżone.Wnajlepszych(metaheurystykachiichhybrydach)trajektoriaobliczeńjest
kierowanaw”obiecująceobszaryzbiorurozwiązań”,któresąnastępnieprzeszukiwane.
Wmonografiiprzedstawiononowepodejściedokonstruowaniaalgorytmówoptymalizacji
dyskretnej,wktórymwceluzwiększeniaefektywnościprzeszukiwaniawykorzystanebędą
nietylkowłasnościogólneproblemu,aletakżewłasnościrozwiązywanejinstancjiproble-
muorazanalizazbiorudanychgenerowanychpodczasprzeszukiwania.Podejścietojest
wynikiemnowegokierunkubadań,tzw.analizykrajobrazuprzestrzenirozwiązań(ang.
landscapeanalysis).Pomimo,żeprzestrzenierozwiązańposzczególnychinstancjiproble-
muznaczniesięróżnią,tojednakposiadająwielecechwspólnych.Możnazaobserwować
