По мотивам семинара Генетические алгоритмы Рахима Давлеткалиева. Такие записи.
Верите ли вы в эволюцию или нет? Очень странный вопрос. Он похож на «верите ли вы в гравитацию?» Это факт, ведь мы наблюдаем эволюцию. Так же, как любые физические явления.
Ответы на стандартные вопросы
Эволиция — это теория. Причем в смысле научная теория. Это лишь так случайно совпало, что в быту слово «теория» имеет значения: предположение, гипотеза. Научная теория объясняет какой-либо процесс (в данном случае процесс эволюции).
Про научные теории, кстати, хорошо сказано в книге «Кратчайшая история времени» Стивена Хокинга:
Любая теория хороша, если она удовлетворяет двум требованиям:
- точно описывает большой класс наблюдений на основе модели, содержащей всего несколько произвольных элементов;
- позволяет делать точные предсказания о результатах будущих наблюдений.
Там же приводится пример. Была теория всемирного тяготения Ньютона, которую и сейчас применяют на практике. Но на поверку оказалось, что ее прогнозы не всегда совпадают с реальностью: так Меркурий двигается не совсем так, как предсказывал Ньютон. Зато все получается, если применить теорию относительности Эйнштейна. Если научная теория хоть раз ошибется, то она неправильная.
Но эволюция на даный момент еще ни разу не ошиблась. Более того, мы постоянно находим всё новые и новые подтверждения. И это не только находки ископаемых: динозавров, мамонтов, древних людей. На самом деле нам еще очень повезло, что мы хоть что-то нашли. Поэтому вопросы, где все звенья эволюции и почему их не найти, не самые важные. Есть достаточное число других факторов, говорящих в пользу теории: на момент выпуска «О происхождении видов» Дарвина ни о каких находках речи даже не шло.
Стоит одельной строкой упомянуть, что эволюция не дает ответов на вопросы, как возникла Вселенная и как появилась жизнь на планете. Бог? Инопланетяне? Большой взрыв? Это не важно данная теория объясняет, как развивалась жизнь, и ей не важно, как эа жизнь произошла.
Некоторые утверждают, что зарождение жизни — это случайность. Даже за те пять миллиардов лет, что существует Земля, вероятность появления не больше, чем если случайным образом перетасовать колоду карт и после этого получить их отсортированными по мастям и весам.
Эволюция — антоним случайности. Если продолжать проводить анлогию с картами, то эволюция говорит так. Перетасуем колоду, выберем карты, которые сложились по порядку, перетасуем оставшиеся, повторим процесс. И так до тех пор, пока все карты не сложатся в правильную последовательность.
Наконец, еще один популярный вопрос. Почему обезьяны до сих пор существуют, если мы произошли от них. Все просто. Во-первых, мы произошли не от обезьян, а от их предков (мы скорее братья обезьян, чем их потомки). Во-вторых, появление нового вида не всегда ведет к исчезновению старого. Если они разойдутся географически и не будут друг другу мешать, то в чем проблема?
Важнейшие факты
- Индивидумов рождается больше, чем способна выдержать вся система. То есть больше, чем способно выжить. Именно это приводит к конкуренции.
- У разных организмов разные черты, разные шансы на выживание и разные шансы на воспроизведение потомства. Это тот самый естественный отбор, о котором говорят в школе.
- Черты организмов — наследуемые. У сильных рождаются сильные детеныши, у слабых не рождается никто, потому что они умирают сами.
Генетический алгоритм
Генетитеский алгоритм — эвристический алгоритм (у которого не всегда есть цель, но который работает в известных случаях). Пример аналогии, лежащий на поверхности — задача коммивояжера.
Как это примерно выглядит? У нас есть набор решений (популяций), которые мы можем сравнивать по близости к лучшему. Далее мы скрещиваем лучшие решения различными способами и производим мутации.
Лирическое отступление. В каждой клетке есть митохондрия — энергетический комплекс клетки. По одной из теорий когда-то это был отдельный организм, но затем клетки его поглотили и образовался симбиоз. Фишка в том, что ДНК митохондрии передаются по материнской линии. Это значит, что мы получаем 50% стандартных генов от отца, 50% генов от матери, плюс гены для митохондрии только от матери. Так что я больше в маму.
Но когда мы решаем задачу и сами скрещиваем решения мы можем брать любые соотношения, не только 50/50. До каких пор мы это делаем — не ясно. Но в любом случае нам необходимо оценивать решения.
Для этого существует fitness function (численная оценка каждого решения). Есть еще две функции: crossover function (разные виды скрещивания, выбираем сами) и mutation function (разные виды мутации, измение каких-то битов).
Возникающие вопросы и проблемы
- Как представлять решения? В бинарном виде, потому что с ними удобно работать.
- Как оценивать решения? Придумать фитнес-функцию.
- Решить как скрещивать и насколько активно использовать мутацию.
- Локальный оптимум. Мы можем застрять на несовершенном решении.
- Задача разрешимости (на котоые должен быть ответ да или нет) не решаются.
- Оценить решение сложно (можем ошибиться и пойти не в том направлении).
Решаемые задачи
- Расписание (диспечеризация)
- Глобальная оптимизация (в сопромате)
- Лингвистический анализ
- Инженерия, дизайн, механика
- Искусственное творчество
- Тестирование приложений
Генетические алгоритмы относятся к разделу эволюционного моделирования, которое является частью такого раздела как искусственный интеллект. Подразделом эволюционных алгоритмов является эволюционное программирование. Это из серии посадить миллион обезьян нажимать клавиши на клавиатуре, чтобы они напечатали «Войну и мир». В некоторых областях это реально работает.
