Голландтың схема теоремасы: генетикалық алгоритмдердің негізгі қағидасы
Holland's schema theorem
Голландтың схема теоремасы: генетикалық алгоритмдердің эволюциялық динамикасы, схемалардың жиілігі мен сәттілігін анықтайды. Негізгі тұжырымдар мен сын.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Голландияның схема теоремасы, сонымен қатар генетикалық алгоритмдердің негізгі теоремасы деп аталады, эволюциялық динамика теңдеуін жуықтау нәтижесінде туындайтын теңсіздік. Схема теоремасы орташа жарамдылықтан жоғары қысқа, төмен дәрежелі схемалардың кезекті ұрпақтарда жиілігі экспоненциалды түрде артатынын айтады. Теореманы Джон Холланд 1970 жылдары ұсынған. Бастапқыда ол генетикалық алгоритмдердің қуатын түсіндірудің негізі ретінде кеңінен қабылданды. Алайда, оның салдарына қатысты осы түсіндірме бірнеше жарияланымда сынға ұшырады, онда Схема теоремасы схемалық индикатор функциясы макроскопиялық өлшем ретінде қолданылатын Баға теңдеуінің ерекше жағдайы екені көрсетілген. Схема – белгілі бір тізбек позицияларында ұқсастығы бар тізбектердің ішкі жиынын анықтайтын үлгі. Схемалар цилиндрлік жиынтықтардың ерекше жағдайы болып табылады және осылайша топологиялық кеңістік құрайды.
Holland's schema theorem, also called the fundamental theorem of genetic algorithms, is an inequality that results from coarse graining an equation for evolutionary dynamics. The Schema Theorem says that short, low order schemata with above average fitness increase exponentially in frequency in successive generations. The theorem was proposed by John Holland in the 1970s. It was initially widely taken to be the foundation for explanations of the power of genetic algorithms. However, this interpretation of its implications has been criticized in several publications reviewed in, where the Schema Theorem is shown to be a special case of the Price equation with the schema indicator function as the macroscopic measurement. A schema is a template that identifies a subset of strings with similarities at certain string positions. Schemata are a special case of cylinder sets, and hence form a topological space.
Сипаттама
6 ұзындығы бар екілік тізбектерді қарастырайық. 1*10*1 схемасы 1, 3 және 6 орындарында 1-ге, ал 4 орындарында 0-ге ие 6 ұзындығындағы барлық тізбектер жиынын сипаттайды. * – бұл жол таңбасы, яғни 2 және 5 орындары 1 немесе 0 мәнін қабылдай алады. Схеманың реті – үлгідегі бекітілген орындардың саны, ал анықталатын ұзындығы – бірінші және соңғы нақты орындар арасындағы қашықтық. 1*10*1 схемасының реті 4, ал оның анықталатын ұзындығы 5-ке тең. Схеманың сәйкестігі – бұл схемаға сәйкес келетін барлық тізбектердің орташа сәйкестігі. Тізбектің сәйкестігі – бұл кодталған мәселенің шешімінің мәні, ол мәселеге қатысты бағалау функциясымен есептеледі. Генетикалық алгоритмдердің белгіленген әдістері мен генетикалық операторларын қолдана отырып, схема теоремасы орташадан жоғары сәйкестігі бар қысқа, төмен реттік схемалар кезекті ұрпақтарда экспоненциалды түрде өседі деп мәлімдейді. Теңдеу түрінде көрсетілген:
Consider binary strings of length 6. The schema 1*10*1 describes the set of all strings of length 6 with 1's at positions 1, 3 and 6 and a 0 at position 4. The * is a wildcard symbol, which means that positions 2 and 5 can have a value of either 1 or 0. The order of a schema is defined as the number of fixed positions in the template, while the defining length is the distance between the first and last specific positions. The order of 1*10*1 is 4 and its defining length is 5. The fitness of a schema is the average fitness of all strings matching the schema. The fitness of a string is a measure of the value of the encoded problem solution, as computed by a problem specific evaluation function. Using the established methods and genetic operators of genetic algorithms, the schema theorem states that short, low order schemata with above average fitness increase exponentially in successive generations. Expressed as an equation:
Мұнда – схемаға жататын тізбектердің саны , – схеманың байқалатын орташа сәйкестігі және – ұрпақта байқалатын орташа сәйкестік. Бұзу ықтималдығы – кроссовердің немесе мутацияның схеманы жоятын ықтималдығы. егер деп есептесек, оны былай көрсетуге болады:
Here is the number of strings belonging to schema at generation , is the observed average fitness of schema and is the observed average fitness at generation The probability of disruption is the probability that crossover or mutation will destroy the schema Under the assumption that , it can be expressed as:
мұнда – схеманың реті, – кодтың ұзындығы, – мутация ықтималдығы және – кроссовер ықтималдығы. Осылайша, қысқа анықталатын ұзындығы бар схема бұзылуы аз. Көптеген адамдардың түсініксіз санайтын мәселе – схема теоремасы теңдік емес, теңсіздік болып табылатыны. Жауап шын мәнінде қарапайым: теорема схемаға жататын тізбектің алдыңғы ұрпақта жатпаған бір тізбектің (немесе екі тізбектің) мутациясы арқылы "құрылуының" шағын, бірақ нөлдік емес ықтималдығын ескермейді. Сонымен қатар, өрнегі анық пессимистік: жұптасу серігіне байланысты рекомбинация схеманы бұзбауы мүмкін, тіпті қиылысу нүктесі бірінші және соңғы бекітілген орындар арасында таңдалған жағдайда да.
where is the order of the schema, is the length of the code, is the probability of mutation and is the probability of crossover. So a schema with a shorter defining length is less likely to be disrupted. An often misunderstood point is why the Schema Theorem is an inequality rather than an equality. The answer is in fact simple: the Theorem neglects the small, yet non zero, probability that a string belonging to the schema will be created "from scratch" by mutation of a single string (or recombination of two strings) that did not belong to in the previous generation. Moreover, the expression for is clearly pessimistic: depending on the mating partner, recombination may not disrupt the scheme even when a cross point is selected between the first and the last fixed position of .
Шектеу
Схема теоремасы шексіз үлкен популяцияны сақтайтын генетикалық алгоритм болжамында қолданылады, бірақ әрқашан (шекті) практикада осылай болмайды: бастапқы популяциядағы үлгі алу қателігі салдарынан генетикалық алгоритмдер ешқандай таңдау артықшылығы жоқ схемаларға жиналуы мүмкін. Бұл әсіресе көп нүктені оптимизациялауда (мультимодальдық оптимизацияда) болады, онда функцияның бірнеше максимумдары болуы мүмкін: популяция басқаларын назарға алмай, бір максимумға қарай жылжуы мүмкін. Схема теоремасы генетикалық алгоритмдердің тиімділігін түсіндіре алмайтынының себебі – ол барлық мәселелерге қатысты, және генетикалық алгоритмдер нашар жұмыс істейтін мәселелер мен жақсы жұмыс істейтін мәселелерді ажырата алмайды.
The schema theorem holds under the assumption of a genetic algorithm that maintains an infinitely large population, but does not always carry over to (finite) practice: due to sampling error in the initial population, genetic algorithms may converge on schemata that have no selective advantage. This happens in particular in multimodal optimization, where a function can have multiple peaks: the population may drift to prefer one of the peaks, ignoring the others. The reason that the Schema Theorem cannot explain the power of genetic algorithms is that it holds for all problem instances, and cannot distinguish between problems in which genetic algorithms perform poorly, and problems for which genetic algorithms perform well.