48 државни капитоли за 8 1/2 дена
Олсон воспоставил низа премиси кои ќе ги одредат неговите подоцнежни пресметки. На прво место, целта не беше да се посетат градовите, туку што е можно повеќе државни капитоли . На второ место, би патувал само со автомобил , што ја остава Алјаска надвор од рутата, поради неговата оддалеченост, и Хаваите, поради потребата да се земе авион, ограничувајќи ја рутата на 48-те соседни држави. Трето и последно, Ќе бидат исклучени правците кои бараат минување низ други земји да се избегнат пасоши и гранични контроли кои го забавуваат секое патување, објаснува Рандал С. Олсон на својата веб-страница.
Земајќи го ова предвид, истражувачот користеше комбинација од генетски алгоритми, Google Maps и повеќецел оптимизација на Парето , или што е истото, открија дека совршенството претпоставува на патување низ САД посета на 48 државни капитоли кои патуваат 21.420 км за 8 и пол дена . Се разбира, додека нема сообраќај. Дополнително, утврди дека патувањето може да се започне од која било точка на рутата без да се менува конечниот резултат.
Како што направи? Со списокот на капитолите во рака, Олсон мораше да утврди кое е вистинското растојание, по пат, а не на права линија, помеѓу овие згради. За да го направите ова, се сврте кон Google Maps API, кој ги пресмета растојанијата на 2.256 можни рути.
Со пресметаните рути, следно беше да ги нарачате за нивната комбинација да резултира со најмал можен број поминати километри. Генетскиот алгоритам го имаше одговорот. Нејзиниот интерес лежи во тоа што, наместо да ги бара сите можни опции, дава случајни решенија, секогаш пробувајќи нешто различно и задржувајќи ги најдобрите предлози, додека не може да најде подобар.
Сето ова во комбинација со примената на Парето повеќецелната оптимизација , што овозможува оптимизирање на повеќе критериуми во исто време. Во овој случај при рака, ќе го максимизира бројот на држави што треба да се посетат и ќе го минимизира времето потребно за тоа.