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

Question

В настоящее время я изучаю генетические алгоритмы (личные, необязательные), и я столкнулся с некоторыми темами, которые мне незнакомы или просто в основном знакомы, и они:

• Пространство поиска
• Экстрим функции

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

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

Answer 1

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

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

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

У этого итеративного подхода есть проблема, заключающаяся в том, что алгоритм может легко "застрять" в локальном экстремуме (при попытке улучшить решение), не зная, что где-то еще есть потенциально лучшее решение:

На рисунке показано, что для достижения реального оптимального решения (минимум global ) алгоритм, который в настоящее время исследует решение вокруг минимума local , должен "перепрыгнуть" за "большой максимум в пространстве поиска. Генетический алгоритм быстро найдет такие локальные оптимумы, но, как правило, ему не удастся «пожертвовать» этой краткосрочной выгодой, чтобы получить потенциально лучшее решение.

Итак, резюме будет:

• исчерпывающий поиск

  • проверяет все пространство поиска (длительное время)

  • находит глобальные крайности

• эвристика (например, генетические алгоритмы)

  • проверяет часть пространства поиска (короткое время)

  • находит локальные крайности

Answer 2

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

"ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ВЫБОРА ФУНКЦИЙ ИНФОРМАЦИОННОГО ОСНОВАНИЯ ОТ ВНУТРЕННЕГО УПАКОВКИ ПАКЕТА С ПРИМЕНЕНИЕМ ИДЕНТИФИКАЦИЯ КОРРОЗИИ С ИСПОЛЬЗОВАНИЕМ АКУСТИЧЕСКОЙ ЭМИССИИ "

http://gbiomed.kuleuven.be/english/research/50000666/50000669/50488669/neuro_research/neuro_research_mvanhulle/comp_pdf/Chemometrics.pdf

Answer 3

Термин «пространство поиска» не ограничивается генетическими алгоритмами.Я на самом деле просто имею в виду набор решений вашей задачи оптимизации .«Экстремум» - это одно решение, которое минимизирует или максимизирует целевую функцию по отношению к пространству поиска.

Answer 4

Пространство диапазона обычно требует некоторого интуитивного понимания проблемы, которую вы пытаетесь решить, - некоторого опыта в этой области.На самом деле нет гарантированного способа выбора диапазона.

Экстремумы - это просто минимальное и максимальное значения функции.

Так, например, если вы кодируете GA только для практики, чтобы найти минимум, скажем, f (x) = x ^ 2, вы очень хорошо знаете, что ваш диапазон должен быть +/- что-то , потому что вы уже знаете, что вы найдете ответпри х = 0.Но тогда, конечно, вы не будете использовать GA для этого, потому что у вас уже есть ответ, и даже если вы этого не сделаете, вы можете использовать исчисление, чтобы найти его.

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

Answer 5

В общем, «пространство поиска» означает, какой тип ответов вы ищете.Например, если вы пишете генетический алгоритм, который строит мосты, тестирует их, а затем строит больше, то ответы, которые вы ищете, - это модели мостов (в некоторой форме).В качестве другого примера, если вы пытаетесь найти функцию, которая согласуется с набором входных данных для некоторого числа точек, вы можете попытаться найти полином с этим свойством.В этом случае ваше пространство поиска может быть полиномами.Вы можете упростить это, установив ограничение на число членов, максимальную степень полинома и т. Д. Таким образом, вы можете указать, что вы хотите искать полиномы с целыми показателями в диапазоне [-4, 4].В генетических алгоритмах пространство поиска - это набор возможных решений, которые вы можете сгенерировать.В генетических алгоритмах вы должны тщательно ограничивать свое пространство поиска, чтобы избежать ответов, которые являются полностью тупыми.В моем бывшем университете студент-физик написал программу, которая представляла собой GA для расчета наилучшей конфигурации атомов в молекуле, обладающей низкоэнергетическими свойствами: они нашли отличное решение, почти не имеющее энергии.К сожалению, их решение поместило все атомы в точный центр молекулы, что физически невозможно :-).ГА действительно оттачивают хорошие решения для ваших функций фитнеса, поэтому важно выбрать пространство поиска так, чтобы оно не давало решений с хорошей подготовленностью, а на самом деле было «невозможным ответом».

Что касается «экстрим "функции.Это просто точка, в которой функция принимает максимальное значение.Что касается генетических алгоритмов, вы хотите лучшее решение проблемы, которую вы пытаетесь решить.Если вы строите мост, вы ищете лучший мост.В этом сценарии у вас есть функция пригодности, которая может сказать вам, что «этот мост может принять 80 фунтов веса» и «этот мост может принять 120 фунтов веса», тогда вы ищите решения, которые имеют более высокие значения пригодности, чем другие.Некоторые функции имеют простые крайности: вы можете найти экстремум полинома, используя простое исчисление средней школы.Другие функции не имеют простого способа вычислить их крайности.Примечательно, что сильно нелинейные функции имеют крайности, которые может быть трудно найти.Генетические алгоритмы превосходны в поиске этих решений, используя умную технику поиска, которая ищет лучшие моменты, а затем находит другие.Стоит отметить, что есть и другие алгоритмы, в том числе и альпинисты.Отличительные черты GA заключаются в том, что если вы найдете локальный максимум, другие типы алгоритмов могут «застрять», ослепленные локально хорошим решением, так что они никогда не увидят, возможно, намного лучшее решение дальше в пространстве поиска.Для этого есть и другие способы приспособления альпинистов, например, имитация отжига.

Answer 6

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

Если вы заинтересованы в генетических алгоритмах, возможно, вы заинтересованы в экспериментах с нашим программным обеспечением.Мы используем его для обучения эвристической оптимизации на уроках.Это графический интерфейс и Windows, так что вы можете начать прямо сейчас.Мы включили ряд проблем, таких как реальные тестовые функции, коммивояжер, маршрутизация транспортных средств и т. Д. Это позволяет вам, например, взглянуть на то, как лучшее решение определенного TSP улучшается в течение нескольких поколений.Это также раскрывает проблему параметризации метаэвристики и позволяет вам найти лучшие параметры, которые будут решать проблемы более эффективно.Вы можете получить его на http://dev.heuristiclab.com.