Вопрос 44:Сорняковый алгоритм.
Общее
Алгоритм сорняковой оптимизации (Invasive Weed Optimization, IWO) вдохновлен таким общераспространенным явлением, как колонизация сельскохозяйственных угодий сорняками. Алгоритм предложен в 2006 г. иранскими учеными Мехрабианом (A.R. Mehrablan) и Лукасом (С. Lucas) и основан на моделировании таких свойств, как посев, рост и конкуренция в колонии сорняка.
Биологические основы
Говоря простым языком, сорняк - это любое растение, растущее там, где оно нежелательно. В общем случае, любое растение может быть классифицировано как сорняк. Однако обычно термин используют по отношению к тем растениям, чьи экспансионистские свойства представляют серьезную угрозу для культивируемых растений. В силу высокой актуальности борьбы с сорняками в мире издается значительное число журналов, полностью посвященных систематике сорняков, их экологии и физиологии, методам контроля и так далее. Наиболее интересной особенностью проблемы сорняков является всеобщее убеждение, что они всегда побеждают, и чем больше люди стараются, тем сильнее они становятся. Пространственные возможности для распространения сорняков создают системы земледелия человека. Сорняки вторгаются в эти пространства с помощью сначала рассеивания семян, затем колонизации и, наконец, оккупации полей. Биоразнообразие сорняков, а также их высокая адаптируемость к местным условиям обеспечивают высокую эффективность указанных процессов. В зависимости от вида растения сорняк может воспроизводиться с использованием или без использования половых клеток. Половое размножение осуществляется с помощью семян, которые формируются в материнском растении после того, как яйцеклетка оплодотворяется пыльцой. Затем эти семена распространяются с помощью ветра, воды, живoтных и так далее (пространственное рассеивание). Если семена попадают в подходящие для жизни условия, они прорастают, вырастают во взрослые растения, затем цветут и производят семена. Основным механизмом, определяющим динамику сообщества любых растений, является естественный отбор, из которого выделяют два крайних типа: r-отбор и К-отбор. Реальные стратегии отбора лежат между этими предельными типами. Можно сказать, что девизом r-отбора является живи быстро, размножайся быстро, умирай молодым (live fast, reproduce quick, die young). Данный тип отбора необходим для успеха в нестабильной, непредсказуемой окружающей среде. При r-отборе предпочтительны такие качества, как высокая плодовитость, маленький размер семян и приспособленность к рассеиванию их на большое расстояние. К-отбор использует принцип живи медленно, размножайся медленно, умирай в старости (live slow, reproduce slow, die old). Этот тип отбора необходим для успеха в стабильной, предсказуемой окружающей среде, когда вероятно тяжелое соперничество за ограниченные ресурсы между конкурентоспособными индивидуумами. Ситуация имеет место, если размер популяции в ареале обитания близок к максимуму, который он способен вместить. При К-отборе предпочтительны такие качества индивидов, как большой размер семян, длинная жизнь, небольшое потомство, за которым требуется интенсивный уход.
Алгоритм
Рассмотрим задачу глобальной безусловной максимизации фитнес-функции. В алгоритме IWO модель поведения сорняков при колонизации учитывает следующие базовые свойства процесса.
- Распределение конечного числа семян по всей области поиска (инициализация популяции).
- Производство выросшими растениями семян в зависимости от приспособленности растений (воспроизводство).
- Распределение произведенных семян в случайном порядке по области поиска (пространственное распределение).
- Повторение шагов 2, 3 до тех пор, пока не будет достигнут заданный максимум числа растений.
- Отбор растений с более высокой приспособленностью, их воспроизводство и пространственное распределение (конкурентное исключение).
- Повторение шага 5 до выполнения условия окончания процесса.
Таким образом, растения и их потомки оцениваются вместе, и тем из них, которые обладают лучшей приспособленностью, позволяют размножаться. Данный механизм позволяет растениям с меньшей приспособленностью воспроизводиться, и, если их потомки обладают хорошей приспособленностью, они могут выжить.
Сравнение
Выполненное авторами алгоритма широкое исследование его эффективности на тестовых функциях «сфера», Гривенка и Растригина показывает, что алгоритм сравним, а в некоторых случаях и лучше таких популяционных алгоритмов, как генетический, меметический, роя частиц и лягушачий.