pingouin 
|
Iesūtīts:
2008.12.29 20:22:51
Ja izzūdi, tad vismaz ieraksti kādu atvadu vēstuli. Piemēram, pasaki, kas Tevi tik ļoti aizvainojis, vai ka esi ļooti aizņemts, vai ka sazin vēl kas. Citādi - parādījies, uzrakstīji mazuliet, izzudi. Un mans tik ķer vēju mežā (t.i. runā ar tukšumu). P.S. Priecīgus Ziemassvētkus.  |
|
pingouin |
# Labojis pingouin: 2009.01.19 13:04:27
Pietam parasti šis optimums jau ir iekodēts pašā algoritma struktūrā... iespējams netieši...
Parādi, kādā veidā nezināmu atrisinājumu var iekodēt ģenētiskajā algoritmā! Un tādu gadījumu, kad ir zināma tikai derīguma funkcija, ir pārāk daudz, lai šim Tavam apgalvojumam būtu pamats.
Ģenētiskie Algoritmi vienmēr darbojas jau predefinētā un Apzinīga Programmētāja noteiktā vērtību apgabalā un domēnā..
Kļūda. Ļoti viegli ir iespējams iekodēt genoma izmēra izmaiņas iespējas - tad vienīgais ierobežojums būtu datora iespējas. (Un, lūdzu, esi tik labs un nelieko lieko vārdu "domēns". Tam jau ir nozīme informātikā (nejaukt ar informācijas teoriju), turklāt tulkojot no angļu `domain`, manuprāt, tā nozīme sakrīt ar `apgabalu`.)
Tas ir tāds savdabīgs meklēšanas algoritms ar permutāciju ģeneratoru kopā sajūgts, un tas tad nu meklē īstenībā n-dimensionālu grafiku kuru izvilkt caur uzdotajiem punktiem ar uzdoto pieļaujamo kļūdu!
Ja ģenētiskajā algoritmā būs iekļauts `sekss` - tad tur nekāds grafiks nesanāks. Turklāt - nezinu nevienu problēmu, kuras risinājums nebūtu iegūts ar kāda "meklēšanas algoritma" palīdzību.
Gan domēns, gan pats algoritms gan uzdotais mērķis ir progarmmā ievadīti lielumi, ko uzdod programmētājs...
Derīguma funkcija nav mērķis (pēc iespējas labāks `organisms`).
Neviens šāds algoritms nekad nav radies spontāni nevienā datorā...
Interesanta doma - "spontāni radīt ģenētisko algoritmu" datorā... |
pingouin |
# Labojis pingouin: 2009.01.19 13:16:33
Man nekad nav nācies dzirdēt par softiem, kas rodas datoros random procesu rezultātā... (Protams, visticamāk, ka šajā gadījumā šis teikums ir izrauts no konteksta, jo oriģinālā Tu laikam biji domājis abioģenēzi datorā. Uz tādu, no konteksta izrautu nabadziņu tad es arī atbildēšu. )
Ģenētiskajos algoritmos ietilpst derīguma funkcija, kā arī vairošanās veids - kas man nešķiet līdzīgi `nejaušiem procesiem`. (Tāpat kā sniegpārsla veidojas nejaušības un dabas likumu rezultātā.)
Par ģenētisko programmēšanu... http://www.genetic-programming.com/humancompetitive.html
P.S.
Sasodīts, bet ideja par abioģenēzi datorā ir ļoti interesanta. Vismaz man kā tējkannai. Lai gan vismaz pirmajā brīdī šķiet, ka dators ir par primitīvu (un pārāk piemērots cilvēka vajadzībām - jo kuram gan vajadzīgi evolucionējoši vīrusi  ) Tur laikam būs jāmaina paša datora arhitektūra...
Ehh... mani tējkannas erotiskie sapņi... |
pingouin |
# Iesūtīts: 2009.01.19 13:34:01
Tur arī viarums Šenona darbu rezultāti - informācijas blīvums uz kanāla kapacitāti etc... No turienes daudzi spiešanas algoritmu ierobežojumi, kontrollsummas etc. etc. etc. Ja esi studējis algoritmu teoriju, tad tur bij kaut kas no sērijas - cik papildus bitus jākomunicē, lai recīveris varētu noteikt kļūdas esamību komunicētajā virknē... Cik papildus biti jākomunicē, lai noteiktu KUR kļūda komunikācijā ir notikusi... Nu tādas lietas... Un ir pilnīgi do feņi KAS tiek komunicēts!
Spiešanas algoritmi laikam tomēr nebija Šenona interešu lokā. Un arī algoritmu teorija man saistās tomēr ar kaut ko citu, nevis ar kļūdas atklājošajiem un labojošajiem kodiem.
Citādi normāli. |
Mulders  |
# Iesūtīts: 2009.01.19 14:02:17
Pingvīn, bet es tak tev saku, ka šī "derīguma funkcija" jau ir ielikta šajos algoritmos!
Rupji runājot... Mums ir algoritms, kurā vēlamais rezultāts jau priekšā ir nolikts. Tad mums ir "šurumburums" tb permutāciju ģenerators, kas ģenerē datus un katri šie dati tiek salīdzināti ar vēlamo rezultātu! Kad dati nonāk vēlamajā kļūdas apgabalā, mēs sakām - esam atraduši optimālo risinājumu!
Nu i? Baigā gudrība... tb atradām to, ko jau sākumā predefinējām, ka meklējam! Tas saucās - front loading. Sistēma, kurā jau iepriekš ir ieprogrammēts tas, kas ir jāsassniedz. Šāda sistēma prasa top-down plānošanu nevis bottom-up meklēšanu uz dullo!
Evoūcija kāreiz ir bottom-up meklēšana to, kas nemaz nav uzdots... Bet visos dzīvajos organismos ir ļoti daudz sistēmas, kuras ir jāuzceļ no pamatblokiem, pirms pati ssitēma sasniedz funkcionalitāti!
Lai peli par sixspārni uztaisītu ir jāveic daudz mērķtiecīas izmaiņas... Nepietiks ka pele no koka lēkā... Jo izdzīvošanas nišas ir vai nu pelei vai sixspārnim, starpposmā nav izdzīvojamās nišas un naturālā selekcija nogalinās jebko, kas būs pus-sixspārnis...
Lai iekšdedzes dzinējs darbotos, nepietiek, ka tiek saliktas 2-3 detaļas, ir jāliek daudz detaļas viena pie otras, kas tikai palielina sistēmas masu nedodot praktiski nekādu labumu sistēmai pašai, tikai tieši pretēji - sliktumu un tikai sasniedzot konkrētu konfigurāciju sistēma var iegūt papildus jaunas fīčas... Taču Naturālā selekcija nokautu jebkuru "liekvārdību"... Savukārt ģenētisks algoritms pēc principa "Vai var existēt" nekad neuzkonstruēs spārnus ar visām papildus sistēmām, kas vajadzīgas lidojumam (elpošanas sistēma, mehāniskā izturība un sistēmas vieglums) |
pingouin |
# Labojis pingouin: 2009.01.19 14:33:34
Rupji runājot... Mums ir algoritms, kurā vēlamais rezultāts jau priekšā ir nolikts. Tad mums ir "šurumburums" tb permutāciju ģenerators, kas ģenerē datus un katri šie dati tiek salīdzināti ar vēlamo rezultātu! Kad dati nonāk vēlamajā kļūdas apgabalā, mēs sakām - esam atraduši optimālo risinājumu!
Es laikam teikšu "muhaha!". Piedod! (Nav skaisti kritizēt neglītu parodiju.)
Derīguma funkcija nosaka tikai "labāk/sliktāk" - tā atrod labākos `organismus` attiecīgajā `paaudzē`. Tā nenosaka `attālumu` no mēģinājumiem līdz jau atrastam atrisinājumam (tas būtu diezgan dumji).
Arī evolūcija ir bez mērķa. |
pingouin |
# Labojis pingouin: 2009.01.19 14:39:14
Es skatos, ka man būs jāpameklē "nereducējamās sarežģītības" paraugi, kas iegūti ģenētisko algoritmu darbības rezultātā.
("Nereducējamā sarežģītība" ir kreacionistu apzīmējums objektiem, kas, no tiem izņemot kādu detaļu, tie `sabruktu`. Skatīt pēdējo Muldera komentāru.) |
Mulders |
# Iesūtīts: 2009.01.19 14:40:47
Derīguma funkcija nosaka tikai "labāk/sliktāk" - tā atrod labākos `organismus` attiecīgajā `paaudzē`. Tā nenosaka `attālumu` no mēģinājumiem līdz jau atrastam atrisinājumam (tas būtu diezgan dumji).
Un tagad mana kārta teikt "Muahaha"
Pēc kādiem kritērijiem tiek noteikts divu random ģenerētu virknīšu "derīgums"
Tieši šis KRITĒRIJS arī ir mērķis predefinētais, kas ir uzdots. Un TAS netiek šajos algoritmos pakļauts random permutācijām!
Jo mērķa funkcija salīdzina konkrētās virknītes kaut kādu, teixim, kontrollsummu un izvēlas to, kura ir "tuvāk" kaut kādam "predefinētam" rezultātam!
Tieši tā evolūcija ir bez mērķa, tāpēc uz to neatteicas ģenētiskie algoritmi, jo tie ir ar mērķi - tie ir frontloaded sistēmas! Evolūcija tāda nav, līdz ar to... uvi... evolūcijai NAV matemātiskā modeļa, kas faktiski šo teoriju pārvērš par just-so pasaku, ne tikai bez empīriskiem laboratoriskiem pierādījumiem, bet pat bez matemātiskā modeļa! |
Mulders |
# Iesūtīts: 2009.01.19 14:41:35
Es skatos, ka man būs jāpameklē "specifiskās sarežģītības" paraugi, kas iegūti ģenētisko algoritmu darbības rezultātā.
Un tu neko nebūsi pierādījis, jo kā jau teicu, Ģenētiskie algoritmi ir front-loaded sistēmas! |
pingouin |
# Iesūtīts: 2009.01.19 14:43:00
Neizdevies Tavs "Muahaha".
Tu uzskati, ka derīguma funkcija "skrien ātrāk!" (piemēram) nosaka visus organisma parametrus? |
Mulders |
# Labojis Mulders: 2009.01.19 14:50:39
Tu uzskati, ka derīguma funkcija "skrien ātrāk!" (piemēram) nosaka visus organisma parametrus?
Nē... tā nosaka atbilstību kaut kādiem uzdotiem parametriem... Tas ir tā, ka atbilstības funkcija uzdod kaut kādus kritiskos punktus uz grafika, caur kuriem grafikam jāiet ar novirzi e (error)... Tādējādi jebkurš grafiks, kas iet caur uzdotajiem punktiem skaitās "labs diezgan". Tad nu ģenētiskais algoritms ģenerē dažādas funkcijas, kas zīmē grafikus un atlasītas tiek tās, kuras vistuvāk uzzīmējas caur uzdotajiem punktiem! Tā tiek noteikts konkrētā grafika "derīgums" salīdzinot ar citiem... Un tā notiekās pakāpeniska aproximācija, kāmēr esam nonākuši uzdotajos parametros!
Kas interesanti, šie ierobežojošie parametri var būt uzdoti pat netieši... ar pašu programmas struktūru...
Un kā jau teicu, ģenētiskajos algoritmos, derīguma funkcija ir konstante faktiski... Tb tā netiek pakļauta "random mutācijām" un pati nekad nav "šurumburums" bet predefinēta tieši vai netieši! Normāls meklēšanas algoritms gadījumiem, kad mums nevajag absolūti precīzu risinājumu! Sarežģītība šim algoritmam ir tuvu n*log(n) tikai tā implementācija ir pietiekoši vienkārša!
To var viegli saprast, ja ģenētisko algoritmu noreducē uz parastu skaitļa atrasānu intervālā no 1 - 100...
Vispārējā gadījumā RND trāpīs "kaut kur pa vidu" un ja vienā reizē tas rāpa tālu no uzdotā skaitļa, tad otrā reizē tas trāpa stipri tuvāk... Net geins ir tā pati dihotomiskā metode, tikai tas parādās pie lieliem iterāciju skaita un lielām datu kopām...
Savukārt ja katrā tavā iterācijā es no jauna iedomājos citu skaitli no 1-100 tad tavs atrašanas ātrums būs vienāds ar pašu RND... tb ir 1/100 čanci ka uzminēsi |
pingouin |
# Iesūtīts: 2009.01.19 14:54:54
evolūcijai NAV matemātiskā modeļa, kas faktiski šo teoriju pārvērš par just-so pasaku, ne tikai bez empīriskiem laboratoriskiem pierādījumiem , bet pat bez matemātiskā modeļa!
Mulders, tēma ir `ģenētiskie algoritmi`. Ja sākšu apspriest arī evolūcijas teoriju, radīsies miljons iespējas aizklīst `ārpustēmās` (radīt "offtopikus" .
So, Empīriskie pierādījumi (fakti)
Ģenētiskā programmēšana.
http://www.aaai.org/AITopics/pmwiki/pmwiki.php/AITopics/GeneticAlgorithms
http://www.genetic-programming.com/humancompetitive.html
Vienkārši ģenētiskie algoritmi
http://www.talkorigins.org/faqs/genalg/genalg.html#examples
http://en.wikipedia.org/wiki/Genetic_algorithm#Applications
(Tie bija daži linki par tēmu "Ģenētisko algoritmu efektivitātes empīriskie pierādījumi: sākumpunkts". Jebšu, mācies meklēt informāciju.) |
Mulders |
# Labojis Mulders: 2009.01.19 15:00:45
Nu un?
Kā jau teicu.. Ģenētiskie algoritmi ir labi algoritmi lai meklētu risinājumus pēc uzdotajiem parametriem. Nu kurā vietā tu te kaut ko nesaproti!
Nu nevar ģenētiskais algoritms, kas programmēts meklēt optimālu tilta konstrukciju, arī kā saidefektu izrēķināt optimālu investīciju programmu akcijām... Tie algoritmi ir jāadaptē konkrētām domēnam un jāuzdod konkrēti parametri pēc kuriem tiek mērīts rezultāta "labums". Tas ka algoritms var šādi atrast LABĀKU risinājumu, ir tikai apsveicami... parādot, ka dators ir ātrāks number krunčers nekā cilvēks! Tak neteiksi ka evolūcija ir patiesa tāpēc, ka kompis ātrāk stabiņā reizina?
Nezinu izklausies ka tu pac no IT nāc... nezinu... vai esi maz rakstījis kādu Ģenētisko Algoritmu pats? A to izklausās, ka kaut ko salasījies un tipiskā Evolucionistu priekā sit plaukstas, neiedziļinoties kas tad tur ir uzrakstīts un kas ir pierādīts vai nepierādīts!
un visa šitā galā... Tas milzīgais prieks, apgalvot, ka Evolūcija IR, jo es uzrakstīju softu, kas dara to vai to... ir... mmm... kaut kā tā... kā apgalvot, ka existē Pūķi un Rūķi, jo ir tāda datorspēle WoW |
pingouin |
# Labojis pingouin: 2009.01.19 15:05:43
Un kā jau teicu, ģenētiskajos algoritmos, derīguma funkcija ir konstante faktiski... Tb tā netiek pakļauta "random mutācijām" un pati nekad nav "šurumburums" bet predefinēta tieši vai netieši! Normāls meklēšanas algoritms gadījumiem, kad mums nevajag absolūti precīzu risinājumu! Sarežģītība šim algoritmam ir tuvu n*log(n) tikai tā implementācija ir pietiekoši vienkārša!
Tava izpratne par derīguma funkciju ģenētiskajos algoritmos ir parodijas izpratne.
Parastam ģenētiskajam algoritmam algoritmam pilnībā pietiek ar "Skrien ātrāk!" veida derīguma funkciju. Tātad - es vēlos dzirdēt, kā šādā derīgumā funkcijā ir noslēpts vēl neatrastais labākais risinājums.
No kurienes tu ieguvi to sarežģītību O(n*log n)?
Tāda sarežģītība ir kārtošanas algoritmiem, ja var noteikt tikai "lielāks/mazāks". Un tad jau no sakārtotās secības Tu piedāvā atrast labāko risinājumu? Tad zini, tāda sarežģītība ir tikai viendimensionāla datu masīva gadījumā. Reālās optimizācijas problēmas nav viendimensionālas.
Varu arī citādāk.
Ņemam ceļojošā pastnieka problēmu (http://en.wikipedia.org/wiki/Postman_problem). Tas ir meklēšanas uzdevums, kurā jāatrod labākais maršruts, taču sarežģītība nav izsakāma ar polinomu - tā ir eksponenciāla.
Pretruna - kas arī bija jāpierāda. |
pingouin |
# Labojis pingouin: 2009.01.19 15:09:37
Kā Tu pamanīji, es jau izteicu savu attieksmi pret evolūciju šajā tēmā. Tā ir offtopiks.
Manu smadzeņu operatīvā atmiņa ir ierobežota, tāpēc esmu ar mieru aplūkot tikai vienu tēmu šobrīd - jebšu ģenētiskos algoritmus.
(Par Tavu pārādīšanos šeit man arī ir jāpateicas tieši ģenētiskajiem algoritmiem. )
Apmaiņai pret šādu vienpusību apsolos ietilpt tikai šajā tēmā. |
pingouin |
# Iesūtīts: 2009.01.19 15:13:58
<< Tas ka algoritms var šādi atrast LABĀKU risinājumu, ir tikai apsveicami... parādot, ka dators ir ātrāks number krunčers nekā cilvēks! Tak neteiksi ka evolūcija ir patiesa tāpēc, ka kompis ātrāk stabiņā reizina? >>
Ideja ir salīdzinājumā starp vienkāršajiem meklēšanas algoritmiem un ģenētiskajiem algoritmiem. Starp to efektivitāti. Nevis starp cilvēka un datora skaitļošanas jaudām. |
Mulders |
# Iesūtīts: 2009.01.19 15:16:40
Parastam ģenētiskajam algoritmam algoritmam pilnībā pietiek ar "Skrien ātrāk!" veida derīguma funkciju. Tātad - es vēlos dzirdēt, kā šādā derīgumā funkcijā ir noslēpts vēl neatrastais labākais risinājums.
Skrien ĀTRĀK! Neviens dators nesaprot... Bet gan šis "ātrāk" tiek implementēts kaut vai kā algoritma performances salīdzinājums! ŠEIT mērķis ir uzdots ar konkrēto parametru... Tb tiek maximizēts viens vai vairāki parametri... NU UN TAD! Tas ir tāpat kā uzlikt kaut kādus uzdotus punktus bezgalībā... Tb ir jau predefinēts slēptais mērķis! Maximizēt ātrumu! To nosaka cilvēks, progarmmētājs... Kā arī iemāca sistēmai NOVĒRTĒT šo ātrumu...
Tāda sarežģītība ir kārtošanas algoritmiem, ja var noteikt tikai "lielāks/mazāks". Un tad jau no sakārtotās secības Tu piedāvā atrast labāko risinājumu? Tad zini, tāda sarežģītība ir tikai viendimensionāla datu masīva gadījumā. Reālās optimizācijas problēmas nav viendimensionālas.
Tāda sarežģītiba ir labākajiem kārtošanas algoritmiem! Un to nepārspēj arī ģenētiskie algoritmi. Loģiski, ka ģenētiskie ir n-dimensionāli, viņiem arī sarežģītība būs salīdzināma ar n-dimensionālajiem labākajiem kārtošanas algoritmiem... Jeb vispār ar log(n) ja iet runa par meklēšanas algoritmiem!
Ņemam ceļojošā pastnieka problēmu (http://en.wikipedia.org/wiki/Postman_problem). Tas ir meklēšanas uzdevums, kurā jāatrod labākais maršruts, taču sarežģītība nav izsakāma ar polinomu - tā ir eksponenciāla.
Pretruna - kas arī bija jāpierāda.
Tieši tā... un Ģenētiskais algoritms lai atrastu LABĀKO risinājumu vispārējā gadījumā būs pilnīgais perebors. bet atrast "Pietiekoši Labu" viņš var gana ātri!
Taču kā jau teicu... Šīs ģenētiskais algoritms jau sevī ENCODĒ to ko tu gribi meklēt! Tb encodēts ir uzdevums, ka jāapmeklē tur visas pilsētas... patērējot minimālu benzīna daudzumu! A ja uzdevumu pamaina uzdevuma gaitā... tad ģenētiskais algoritms aiziet pa pieskari!
Un vēlreiz, tas atrod LABU risinājumu, tas neatrod LABĀKO... jeb ja tu ģenētiskajam algoritmam šo error uzdosi ar 0 tas var nokonverģēt uz pilnās pārlases algoritmu pietam ar lielu risku iekrist lokālajā otpimumā, bez iespējas vispār atrast risinājumu!
Ponta pēc padarbini onlainā atrodamos šī algoritma pielietojumus kāreiz šai problēmai - redzēsi, ka 2x palaists uz pietiekoši liela pilsētu skaita, tas dos dažādus risinājumus, bet ja uzdosi uzdevumu atrast VISLABĀKO... var sanākt iet kafiju dzert! |
pingouin |
# Iesūtīts: 2009.01.19 15:17:36
Interesanti, vai ģenētiskās programmēšanas gadījumā informācija nekādi nepalielinās? Kad attīstās programmas, kas risina noteiktus uzdevumus. |
Mulders |
# Iesūtīts: 2009.01.19 15:18:55
Ideja ir salīdzinājumā starp vienkāršajiem meklēšanas algoritmiem un ģenētiskajiem algoritmiem. Starp to efektivitāti. Nevis starp cilvēka un datora skaitļošanas jaudām.
Lasi pēdējo postu!
Ģenētiskais algoritms atrod "pietiekoši labu" nevis "labāko"!
Kaut vai klasiskā... funjkcijas optimuma atrašana... Elementāri uzraksti ģenētisko algoritmu kas plaknē 2d funkcijai meklē maximumu... un pats pārliecinies, ka tas ne vienmeŗ to atdod, bet gan atrod lokālo optimumu! |
Mulders |
# Iesūtīts: 2009.01.19 15:21:17
Interesanti, vai ģenētiskās programmēšanas gadījumā informācija nekādi nepalielinās? Kad attīstās programmas, kas risina noteiktus uzdevumus.
Nope... Algoritms, kas optimizē tilta konstrukciju nevar pēkšņi arī sākt risināt cita domēna optimizācijas uzdevumus! Algoritms vienmēr risinās tikai un vienīgi konkrētu konstrukciju stiprību... Lai tas varētu sākt risināt akciju tirgus paredzējumus, tas būs jāpārprogrammē!
Teicu jau Ģenētiskais algoritms var optimizēt uzdotu esošu datu kopu... Nevis radīt jaunu! Tb tas var tev optimizēt, piemēram, mājas plānu... Bet viņš tev to māju nekad nepadarīs par automašīnu vai kuģi! |
pingouin |
# Iesūtīts: 2009.01.19 15:39:58
Skrien ĀTRĀK! Neviens dators nesaprot... Bet gan šis "ātrāk" tiek implementēts kaut vai kā algoritma performances salīdzinājums! ŠEIT mērķis ir uzdots ar konkrēto parametru... Tb tiek maximizēts viens vai vairāki parametri... NU UN TAD! Tas ir tāpat kā uzlikt kaut kādus uzdotus punktus bezgalībā... Tb ir jau predefinēts slēptais mērķis! Maximizēt ātrumu! To nosaka cilvēks, progarmmētājs... Kā arī iemāca sistēmai NOVĒRTĒT šo ātrumu...
Mērķis patiesībā ir atrast tādus organisma parametrus, kuri maksimizē šo ātrumu. Un saistība starp reāla daudzdimensiju optimizācijas uzdevuma parametriem un vienu vienīgo derīguma funkciju nav tik vienkārša, lai varētu runāt par "vienkāršu tiekšanos bezgalībā".
Mēs nevis pārvietojamies pa taisni, uz kuras ir atzīmētas visas iespējamās ātruma vērtības (kā pa reālo skaitļu asi no nulles līdz simtniekam), bet gan taustāmies daudzdimensiju telpā, kuras koordinātu sakarība ar derīguma funkciju ir pietiekami sarežģīta, lai apgalvojumi par jau zināmā risinājumu iešifrēšanu ģenētiskajā algoritmā būtu nepamatoti.
Tāda sarežģītiba ir labākajiem kārtošanas algoritmiem! Un to nepārspēj arī ģenētiskie algoritmi. Loģiski, ka ģenētiskie ir n-dimensionāli, viņiem arī sarežģītība būs salīdzināma ar n-dimensionālajiem labākajiem kārtošanas algoritmiem... Jeb vispār ar log(n) ja iet runa par meklēšanas algoritmiem!
Ja ir runa par maksimuma atrašanu, tad vajadzēs vismaz n.
Tieši tā... un Ģenētiskais algoritms lai atrastu LABĀKO risinājumu vispārējā gadījumā būs pilnīgais perebors. bet atrast "Pietiekoši Labu" viņš var gana ātri!
Daudzas reizes ātrāk par jebkuru vienkāršu meklēšanas algoritmu. Un šis "pietiekoši labi" atsver milzīgo laika ietaupījumu ar patiešām labākā risinājuma meklējumiem. Kā jau teicu, šai problēmai tiešām labākā risinājuma atrašanai nepieciešams polinomiāls laiks.
Vispār pretenzijas bija pret Tavu jocīgo sarežģītību n*log n. (Jo pastnieka problēmas gadījumā tā sanāktu pilnīgi droši lielāka.)
Taču kā jau teicu... Šīs ģenētiskais algoritms jau sevī ENCODĒ to ko tu gribi meklēt! Tb encodēts ir uzdevums, ka jāapmeklē tur visas pilsētas... patērējot minimālu benzīna daudzumu! A ja uzdevumu pamaina uzdevuma gaitā... tad ģenētiskais algoritms aiziet pa pieskari!
Kļūda. "Enkodēta" ir tikai derīguma funkcija, kas nosaka tikai patērēto benzīna daudzumu (ko izmanto, salīdzinot savstarpējo organismu derīgumu), kā arī paša organisma uzbūve (tam jāsavieno visas pilsētas). Pats maršruts nav enkodēts. Kā Tu no derīguma funkcijas un organisma veida noteiksi sakarīgu maršrutu?
Ponta pēc padarbini onlainā atrodamos šī algoritma pielietojumus kāreiz šai problēmai - redzēsi, ka 2x palaists uz pietiekoši liela pilsētu skaita, tas dos dažādus risinājumus, bet ja uzdosi uzdevumu atrast VISLABĀKO... var sanākt iet kafiju dzert!
Kā jau rakstīju, pretenzija bija vērsta pret mītisko sarežģītību n*log n. Piedod, ja Tu mani pārprati.
Ģenētiskie algoritmi nemeklē globālo maksimumu. Jo praksē pietiek arī ar pietiekami (pat ļoti pietiekami) labiem risinājumiem. |
:: Pievienot komentāru
|
