Эволюционные вычисления в технических задачах

Авторы статьи: Ю.А. Скобцов

Источник: Пленарні доклади/ Інформаційні управляючі системи та технології та комп'ютерний моніторінг (ІУС та КСМ 2010). – 2010. – С.30-34.

Аннотация

Скобцов Ю.А.Эволюционные вычисления в технических задачах.Представлено новое направление в теории искусственного интеллекта - эволюционные вычисления, включающие генетические алгоритмы, генетическое программирование, эволюционные стратегии и эволюционное программирование. Рассматривается применение этого нового аппарата на примере задач автоматизации проектирования и обработки изображения.

Введение

Для повышения уровня “интеллекта” и эффективности современных методов решения прикладных технических задач, расширения их возможностей применяются различные методы искусственного интеллекта. Одним из самых перспективных направлений является использование эволюционных вычислений (ЭВ)[1].

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

1. генетические алгоритмы (ГА

2. эволюционные стратегии (ЭС);

3. эволюционное программирование (ЭП);

4. генетическое программирование (ГП).

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

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

Генетические алгоритмы представляют собой алгоритмы случайного направленного поиска для построения (суб)оптимального решения данной проблемы, который моделирует процесс естественной эволюции. Классический “простой” ГА использует двоичные строки для кодирования решения проблемы – особи (хромосомы) [1]. Это делает его привлекательным для использования во многих прикладных технических задачах, где решение задачи представляется в виде двоичных наборов или их последовательностей [1,2]. Множество потенциальных решений образует популяцию особей, которая в процессе поиска решения эволюционирует благодаря искусственным генетическим операторам отбора, скрещивания и мутации. В ГА на множестве решений определяется целевая (фитнесс) функция (ЦФ), которая позволяет оценить близость каждой особи к оптимальному решению. В простом ГА применяются три основных оператора: репродукция, кроссинговерскрещивание, мутация. Используя данные операторы, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению, что можно представить следующей последовательностью действий.

1. Создание исходной популяции.

2. Оценка значений фитнесс-функций особей текущей популяции.

3. Выбор родителей для процесса размножения (работает оператор отбора - репродукции).

4. Создание потомков выбранных пар родителей (работает оператор скрещивания - кроссинговер).

5. Мутация новых особей (работает оператор мутации).

6. Расширение популяции новыми порожденными особями.

7. Сокращение расширенной популяции до исходного размера (работает оператор редукции).

8. Если критерий останова алгоритма выполнен, то выбор лучшей особи в конечной популяции – результат работы алгоритма. Иначе переход на шаг 2.

В настоящее время предложены многочисленные модификации и обобщения ГА [1], в которых: 1) разработаны различные варианты реализации каждого этапа; 2) существенно изменена структура алгоритма. Среди первой группы можно выделить различные методы отбора родителей (пропорциональный, турнирный, локальный, ранжирование и т.д.), сокращения популяции (элитарный, случайный, пропорциональный, селекционный и т.д.). Разработаны различные генетические операторы кроссинговера двоичных (одноточечный, многоточечный, однородный) и действительных значений (дискретная, промежуточная, линейная рекомбинация), мутации (однородная и неоднородная для двоичных и вещественных значений). Среди второй группы можно отметить ГА с динамически изменяемой мощностью популяции (различные стратегии выбора срока жизни особи), адаптивные ГА с подстраиваемыми параметрами (вероятности кроссинговера и мутации), параллельные алгоритмы (модель островов, глобальная модель рабочий-хозяин, диффузионная модель), иерархические (многоуровневые) ГА [1].

В науке и технике эволюционные вычисления используются в качестве адаптивных алгоритмов для решения практических задач и как вычислительная модель эволюции естественных систем. ЭВ успешно применяются при решении сложных задач в технических разработках и в бизнесе. С помощью ЭВ было разработано много промышленных проектных решений, которые позволили сэкономить миллионы долларов. ЭВ широко используются для прогнозирования развития финансовых рынков, инвестиций и т.п. Методы ЭВ обычно используются для оценки и выбора (суб)оптимальных непрерывных параметров моделей большой размерности, для решения различных NP-полных комбинаторных задач, в системах извлечения знаний из больших баз данных (Data mining) и многих других областях науки и техники. Следует отметить, что когда задача не может быть решена другими, более простыми методами, ЭВ часто могут найти оптимальные или близкие к ним решения. При этом объем вычислений может оказаться большим, но скорость, с которой он растет при увеличении размерности задачи обычно меньше, чем у остальных известных методов. После того, как компьютерные системы стали достаточно быстродействующими и недорогими, ЭВ превратились в важнейший инструмент поиска субоптимальных решений задач, которые до этого считались неразрешимыми. Хороший обзор применения ЭВ в различных областях можно найти в серии работ Alander, например, [3]. Далее мы рассмотрим применение ЭВ на примере решения некоторых прикладных технических задач.

Применение ЭВ в САПР.

Эволюционные алгоритмы нашли широкое применение в системах автоматизации проектирования (САПР) компьютерных систем [2], в основном на этапах: 1) логического синтеза; 2) физического проектирования (разбиение, размещение, трассировка); 3) тестирования. Для каждой из этих проблем разработаны множество способов кодирования хромосом, проблемно-ориентированных генетических операторов кроссинговера и мутации и различных видов фитнесс-функций.

На этапе проектирования цифровых схем эволюционные методы применяются на различных уровнях: 1) транзисторный; 2)вентильный; 3) функциональный. При синтезе эволюционный алгоритм используется для поиска конфигурации схемы для того, чтобы достичь ее поведения в соответствии со спецификациями. В этом случае хромосома представляет конфигурацию (схему) либо непосредственно двоичной строкой, либо некоторой более сложной структурой, которую необходимо транслировать в схему. Для вычисления значений фитнесс-функций используется программы моделирования. Как правило, целью является: минимизация различия выходных сигналов со спецификациями.

При эволюционном синтезе малых схем используется транзисторный уровень, где в качестве отдельных компонентов выступают резисторы, емкости и транзисторы. На этом уровне обычно синтезируются новые типы вентилей и триггеров. Следует отметить, что ГА позволяют легко формализовать задачу параметрического синтеза. В простейшем случае хромосома содержит значения параметров схемы (с заданной структурой). Но использование ГП позволяет гораздо больше – формализовать задачу структурного синтеза – поиск структуры схемы. Это возможно вследствие того, что представление хромосом, используемое в ГП (деревья или графы), отражает структуру схемы.

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

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

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

Заключительным этапом конструкторского проектирования является верификация. Одной из важнейших задач верификации является установление взаимно-однозначного соответствия между структурной и электрической схемой СБИС и ее топологической реализации. Эта задача сводится к установлению изморфизма между графом электрической схемы и графом ее топологии.

Даже если схемы корректно спроектированы, значительная часть их (иногда до 70%) после изготовления работают неправильно вследствие наличия физических дефектов вследствие исключительно сложной технологии изготовления. Поэтому чрезвычайно важным является этап тестирования цифровых схем [2]. Здесь ЭВ применяются для генерации тестовых входных воздействий. Применение ГА для построения проверяющих тестов показало их высокую эффективность по сравнению с традиционными методами генерации тестов, в особенности, для последовательностных схем [2]. Самым эффективным в настоящее время является совместное применение и чередование детерминированных и генетических методов генерации тестов. При генерации тестов для микропроцессорных (МП) систем одним из самых перспективных является подход, основанный на генетическом программировании (ГП). Проверяющей последовательностью для МП-систем является тестпрограмма, состоящая из операторов ассемблера, которые удобно представлять ориентированным ациклическим графом (ОАГ) [2]. Для них разработаны свои генетические операторы.

Примененеие ЭВ при обработке и распознавании изображений.

Основной целью компьютерных систем анализа изображений является выделение и распознавание объектов. Одним из основных этапов функционирования таких систем, существенно влияющим на их эффективность, является обработка цифровых изображений. Обобщенно функциональную схему КСАИ можно представить как последовательность этапов: предварительная обработка, выделение границ и сегментация, выделение признаков, распознавание и интерпретация.

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

Рисунок 1 – Результат сегментации изображений гистологического среза лимфатического узла

Следующий этап производит расчет признаков выделенных объектов изображения, позволяющий осуществлять дальнейшее их распознавание и интерпретацию. Например, для изображений гистологических срезов были вычислены такие параметры, как периметр, площадь, эксцентриситет и т.д. На основе рассчитанных параметров осуществляется отнесение клеток на изображении к одному из классов, например, раковые или нераковые. На последних этапах происходит анализ обработанного изображения, а так же представление его полезной составляющей в виде, удобном для специалиста. Следует отметить, что для осуществления автоматической обработки обычно используются априорные знания из базы знаний. В результате анализа применения ЭВ в обработке изображений [4] можно отметить, что при сравнении решений, полученных с помощью классических и эволюционных, последние дают значительно большую точность. В большинстве случаев, методы, основанные на применении ЭВ, превосходят нетрадиционные методы, такие как нейронные сети(НС) и моделирование отжига (МО). Несмотря на то, что время получения решения указано не во всех источниках, можно отметить следующее: 1) результаты, полученные за приемлемое время, указаны в: [4]; 2) неудовлетворительное время получения решения было приведено в [4]. При сравнении с другими методами: 1) обнаружено увеличение скорости получения решения, например, с помощью алгоритмов, основанных на градиентных методах и МО [4]; 2) время решения, методов фактически совпадает; 3) время получения решения с помощью ЭВ больше, чем классическими методами, например [4]. Наибольших временных ресурсов при решении требуют методы, основанные на генетическом программировании, что связано с затратами на стадии обучения.

Выводы.

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

Поэтому при выборе метода решения конкретной задачи предлагается:

1) использование ЭВ, в результате которых получаются приемлемые решения;

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

3) объединение эволюционных с обычными алгоритмами решения конкретной проблемы;

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

5) использование параллельных вычислений для оценки целевой функции.

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

Список литературы

1. Скобцов Ю.А. Основы эволюционных вычислений. Донецк: ДонНТУ, 2008. – 326 с.

2. Скобцов Ю.А., Скобцов В.Ю..Логическое моделирование и тестирование цифровых устройств. – Донецк: ИПММ НАНУ, ДонНТУ, 2005. – 436 с.

3. Alander J. T. An Indexed Bibliography of Genetic Algorithms in Optics and Image Processing. Report Series No. 94-1-OPTICS. Department of Electrical Engineering and Automation University of Vaasa.

4. Скобцов Ю.А., Мартыненко Т.В.. Эволюционные вычисления в обработке изображений // Труды XXXV международного симпозиума «Вопросы оптимизации вычислений». – 2009.