Построение экспериментально-генетического исследования

Оглавление:

Природа поражает своей сложностью и богатством своих проявлений. Примерами могут служить сложные социальные системы, иммунная и нервная системы, а также сложные взаимоотношения между видами. Это лишь некоторые из чудес, которые стали очевидны при глубоком изучении окружающей нас природы. Наука — это одна из систем, которая объясняет происходящее вокруг нас и помогает нам адаптироваться к новой информации из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, изменения и отбор.

На мировоззрение людей большое влияние оказала теория эволюции Чарльза Дарвина, которую он изложил в книге «Происхождение видов» в 1859 году. Многие области научного знания во многом обязаны революции, произведенной эволюцией и эволюционной теорией. Но Дарвин, как и многие его современники, предполагавшие, что эволюция движима естественным отбором, не ошибался. Он не смог, например, показать механизм наследственности, который поддерживает вариации. Однако Дарвин открыл главный механизм эволюции: отбор в сочетании с изменчивостью. Во многих случаях особенности развития путем вариаций и отбора еще не являются бесспорными, но основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в природе. Поэтому неудивительно, что ученые-компьютерщики вдохновлялись эволюционной теорией. Возможность того, что вычислительная система, оснащенная простыми механизмами изменчивости и отбора, может работать по аналогии с законами эволюции в природных системах, была очень привлекательной. Эта надежда послужила причиной появления ряда компьютерных систем, основанных на принципах естественного отбора.

Проблемы оптимизации постоянно возникают в природе. Оптимизационные задачи являются наиболее распространенными и важными на практике. Каждому из нас приходится решать их либо дома, распределяя свое время между различными задачами, либо на работе, пытаясь максимально увеличить скорость работы программы или прибыльность бизнеса, в зависимости от занимаемой должности.

Открытия последних ста лет позволили современной науке выявить все ключевые механизмы эволюции, связанные с генетическим наследованием. Эти механизмы довольно просты по своей идее, но забавны (если это слово применимо к природе) и эффективны. Удивительно, но простое моделирование эволюционного процесса на компьютере может обеспечить решение многих практических проблем. Такие модели называются «генетическими алгоритмами» и уже широко используются в различных областях.

Генетические алгоритмы

Генетические алгоритмы возникли из наблюдений и попыток копирования естественных процессов в мире живых существ, в частности, эволюции и связанного с ней отбора (естественного отбора) популяций живых существ.

Идея генетических алгоритмов была предложена Дж. Холландом в конце 1960-х — начале 1970-х годов. Его интересовали свойства естественных эволюционных процессов, в том числе тот факт, что эволюционируют именно хромосомы, а не сами живые существа. Холланд был убежден в возможности составить алгоритм и реализовать его в виде компьютерной программы, которая будет решать сложные задачи так, как это делает природа — путем эволюции. Поэтому он начал работать над алгоритмами, которые использовали последовательности двоичных цифр (единицы и нули), называемые хромосомами. Эти алгоритмы имитировали эволюционные процессы в поколениях таких хромосом. В них были реализованы механизмы отбора и воспроизводства, аналогичные механизмам естественной эволюции. Генетические алгоритмы, как и в природе, реализуют поиск «хороших» хромосом без какой-либо информации о характере решаемой задачи. Для каждой хромосомы требовалась только оценка, отражающая ее приспособленность. Механизм отбора заключается в выборе хромосом с наивысшим баллом (т.е. лучше приспособленных), которые размножаются чаще, чем особи с более низким баллом (хуже приспособленные). Размножение — это создание новых хромосом путем рекомбинации генов из родительских хромосом. Рекомбинация — это процесс, в ходе которого создаются новые комбинации генов.

Реализация генетических алгоритмов

В природе особи в популяции конкурируют друг с другом за различные ресурсы, такие как пища или вода. Кроме того, члены популяции одного вида часто конкурируют за партнера для спаривания. Те особи, которые лучше всего приспособлены к окружающей среде, имеют относительно более высокие шансы произвести потомство. Слабо приспособленные особи либо вообще не производят потомства, либо их потомство очень мало. Это означает, что гены высокоадаптированных или приспособленных особей будут распространяться во все большем количестве потомков в каждом последующем поколении. Сочетание хороших черт от разных родителей иногда может привести к появлению «супер-адаптированного» потомства, чья приспособленность выше, чем у любого из его родителей. Таким образом, вид эволюционирует, становясь все более приспособленным к окружающей среде.
Генетические алгоритмы используют прямую аналогию с таким механизмом. Они работают с набором «особей», популяцией, каждая из которых представляет собой возможное решение конкретной проблемы. Каждой особи присваивается мера «пригодности», основанная на том, насколько «хорошим» является соответствующее ей решение проблемы. Например, мерой пригодности может быть отношение прочности к весу для конкретной конструкции моста. В природе это эквивалентно оценке того, насколько эффективно организм конкурирует за ресурсы. Наиболее приспособленные особи получают возможность «воспроизводить» потомство путем «скрещивания» с другими особями в популяции. В результате образуются новые особи, сочетающие в себе некоторые черты, унаследованные от родителей. Наименее приспособленные особи имеют меньше шансов произвести потомство, поэтому признаки, которыми они обладали, постепенно исчезают из популяции в ходе эволюции.

Таким образом, вся новая популяция допустимых решений воспроизводится путем отбора лучших представителей предыдущего поколения, их скрещивания и получения множества новых особей. Это новое поколение содержит большую долю признаков, которыми обладали хорошие представители предыдущего поколения. Таким образом, хорошие черты распространяются в популяции из поколения в поколение. Скрещивание наиболее приспособленных особей приводит к исследованию наиболее перспективных областей пространства поиска. В конце концов, популяция сходится к оптимальному решению проблемы.

Применение генетических алгоритмов

Генетические алгоритмы в различных формах применяются для решения многих научных и инженерных задач. Генетические алгоритмы использовались при создании других вычислительных структур, таких как автоматы или сортировочные сети. В машинном обучении они использовались для проектирования нейронных сетей или для управления роботами. Они также использовались для моделирования развития различных тем, включая биологические (экология, иммунология и популяционная генетика), социальные (экономика и политические системы) и когнитивные системы.
Однако, возможно, самым популярным применением генетических алгоритмов является оптимизация многопараметрических функций. Многие проблемы реального мира могут быть сформулированы как поиск оптимального значения, где значение является сложной функцией, которая зависит от некоторых входных параметров. В некоторых случаях интерес представляет поиск тех значений параметров, при которых получается наилучшее точное значение функции. В других случаях точный оптимум не требуется; любое значение, лучшее, чем определенное, может рассматриваться как решение. В этом случае генетические алгоритмы часто являются наиболее подходящим методом для поиска «хороших» значений. Сила генетического алгоритма заключается в его способности манипулировать многими параметрами одновременно. Это свойство генетического алгоритма было использовано в сотнях приложений, включая проектирование самолетов, подгонку параметров алгоритма и нахождение устойчивых систем нелинейных дифференциальных уравнений.

Однако нередко генетический алгоритм работает не так эффективно, как ожидалось. Предположим, существует реальная задача, которая предполагает поиск оптимального решения. Как же узнать, является ли генетический алгоритм хорошим методом для решения этой проблемы? На сегодняшний день строгого ответа нет, но многие исследователи разделяют предположение, что если исследуемое пространство поиска велико и предполагается, что оно не является идеально гладким и унимодальным (т.е. содержит единственный гладкий экстремум) или не очень четким, или если фитнес-функция зашумлена, или если задача не требует строгого нахождения глобального оптимума, т.е, если он достаточно быстр, чтобы просто найти приемлемое «хорошее» решение (что довольно часто случается в реальных проблемах), генетический алгоритм имеет хорошие шансы стать эффективным методом поиска, конкурирующим с другими методами, не использующими знания о пространстве поиска, и превосходящим их.

Однако, когда пространство поиска невелико, решение может быть найдено грубой силой, и можно быть уверенным, что будет найдено наилучшее возможное решение, в то время как генетический алгоритм, скорее всего, сойдется к локальному оптимуму, чем к глобально лучшему решению. Когда пространство гладкое и унимодальное, любой градиентный алгоритм, например, метод наискорейшего спуска, более эффективен, чем генетический алгоритм. Когда имеется некоторая дополнительная информация о пространстве поиска (например, пространство для известной задачи Путешественника-Продавца), методы поиска, использующие эвристики, определяемые пространством, часто превосходят любой универсальный метод, такой как генетический алгоритм. Если топография фитнес-функции достаточно сложна, методы поиска с единственным решением в данный момент времени, такие как метод простого спуска, могут «подключить» локальное решение, но генетический алгоритм, поскольку он работает с целой «популяцией» решений, как предполагается, имеет меньший шанс сходимости к локальному оптимуму, и будет работать устойчиво в ландшафте с множеством экстремумов.

Конечно, такие предположения не всегда предсказывают, когда генетический алгоритм является эффективным методом поиска в конкуренции с другими методами. Эффективность генетического алгоритма в значительной степени зависит от таких деталей, как метод кодирования решений, операторы, настройки параметров и частный критерий успеха. Теоретическая работа, отраженная в литературе по генетическим алгоритмам, не предлагает строгих механизмов для явных предсказаний.

Символьная модель простого генетического алгоритма

Целью оптимизации с помощью генетического алгоритма является поиск наилучшего возможного решения (решений) проблемы на основе одного или нескольких критериев. Чтобы реализовать генетический алгоритм, необходимо сначала выбрать подходящую структуру для представления этих решений. В постановке задачи поиска экземпляр этой структуры данных представляет собой точку в пространстве поиска всех возможных решений.

Структура данных генетического алгоритма состоит из одной или нескольких хромосом. Как правило, хромосома — это битовая строка, поэтому термин «строка» часто заменяет термин «хромосома». В принципе, генетические алгоритмы не ограничиваются двоичным представлением. Известны и другие варианты реализации, основанные исключительно на векторах вещественных чисел. Несмотря на то, что строки переменной длины кажутся более подходящими для решения многих реальных задач, структуры фиксированной длины в настоящее время являются наиболее распространенными и лучше всего изученными. Пока мы ограничимся структурами, которые являются одиночными строками по l бит каждая.

Каждая хромосома (строка) представляет собой конкатенацию ряда субкомпонентов, называемых генами. Гены расположены в разных местах или локусах на хромосоме и принимают значения, называемые аллелями. В двоичном представлении ген — это бит, локус — его положение в строке, а аллель — его значение (0 или 1). Биологический термин «генотип» относится к полной генетической модели особи и соответствует структуре в генетическом алгоритме.

Простой генетический алгоритм случайным образом генерирует начальную популяцию структур. Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не будет достигнуто определенное число поколений или другой критерий остановки. В каждом поколении генетического алгоритма осуществляется пропорциональный отбор, одноточечный кроссовер и мутация. Во-первых, пропорциональный отбор присваивает каждой структуре вероятность Ps(i), равную отношению ее пригодности к общей пригодности популяции:
Затем все n особей (с заменой) отбираются для дальнейшей генетической обработки в соответствии со значением Ps(i). Простейший пропорциональный отбор, колесо рулетки, отбирает людей на основе n «проходов» колеса рулетки. Колесо рулетки содержит один сектор для каждого члена населения. Размер ith сектора пропорционален соответствующему значению Ps(i). При таком отборе члены популяции с более высокой приспособленностью имеют больше шансов быть отобранными, чем члены с более низкой приспособленностью.

После отбора n отобранных особей скрещиваются с заданной вероятностью Pc (иногда это называется рекомбинацией). n линий случайным образом делятся на n/2 пар. Для каждой пары с вероятностью Pc может быть применен кроссинговер. Соответственно, с вероятностью 1-Pc кроссинговер не происходит, и неизмененные особи переходят в фазу мутации. Когда происходит кроссинговер, полученное потомство заменяет своих родителей и переходит к мутации.

Одноточечный кроссинговер работает следующим образом. Сначала случайным образом выбирается одна из точек останова. На этом этапе обе родительские структуры делятся на два сегмента. Затем соответствующие сегменты разных родителей сращиваются вместе, чтобы получить два генотипа потомства.

На странице курсовые работы по психологии вы найдете много готовых тем для курсовых по предмету «Психология».

Здесь темы рефератов по психологии

Читайте дополнительные лекции: