Оценка эффективности генетических алгоритмов поиска масок

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

Вначале приведем утверждение об оценке вычислительной сложности описанных в предыдущей лекции ПГА.

Введем следующие обозначения. Пусть $$K$$ - число этапов эволюции, реализуемых ГА, $$M$$ - число особей в популяции, $$W$$ - объем памяти (в битах) для хранения одной особи.

Теорема. Пусть для ЦУ с множеством неисправностей $$F$$ получен СПР. Тогда оценка алгоритмической сложности одного запуска генетического алгоритма со структурой хромосомы (29.1) или (29.6) и с использованием любой из фитнес-функций (29.3)-(29.5), (29.7)-(29.10) равна $$O(KM\cdot(W\cdot(|F|+1)+\log{M}))$$, а объем памяти, необходимой для работы генетического алгоритма, равен $$O(2MW)$$.

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

Исходя из вида формул (29.3)-(29.5), (29.7)-(29.10), оценка вычислительной сложности для функций приспособленности сводится к оценке вычислительной сложности величин $$\rho_2$$ и $$\rho_6$$. Согласно [1] вычислительная сложность величины оценивается величиной

Для вычисления значения $$\rho_6$$ необходимо также произвести

сравнений. Сортировка элементов популяции производится за время

Принимая во внимание тот факт, что в процессе эволюции должно быть найдено поколений, а также с учетом (30.1) -(30.3) , получим оценку вычислительной сложности, приведенную в формулировке теоремы.

На каждом этапе эволюции требуется хранение двух поколений: родительской популяции и популяции дочерних особей. Отсюда емкостная сложность генетического алгоритма для задач минимизации и оптимизации диагностической информации оценивается величиной $$O(2MW)$$.

Заметим, что один из возможных способов ускорения времени работы ПГА состоит в их распараллеливании.

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

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

Важно заметить, что при такой организации ГА ему безразлично, как и в какой среде передаются сообщения, поэтому этот способ подходит для вычислительных систем любой организации: однопроцессорных ЭВМ, многопроцессорных ЭВМ или кластеров любой структуры. Эффективность такого распараллеливания зависит прежде всего от скорости передачи сообщений между потоками. Если рассматривать многопроцессорную ЭВМ с общей памятью, где скороcть передачи данных между потоками максимальна, то распараллеливание любых операторов эффективно практически во всех случаях, т. к. генотипы, хранящиеся в общей памяти, не копируются для каждого рабочего потока, а используются совместно.

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

Качественные оценки вычислительной сложности ПГА, полученные в сформулированной выше теореме, несомненно представляют интерес, но значительно больший интерес представляют экспериментальные данные, полученные для различных реальных ЦУ. Ниже будет представлена статистика, полученная в результате проведения численных экспериментов как на исходных данных, генерируемых случайным образом, так и на реальной ДИ для некоторых реальных ДУ.

Результаты экспериментов, демонстрируемые ниже в табл. 30.1-30.7, получены на PC Pentium III, 1024 MHz, 256 MB RAM и частично отражены в [5].

Данные об эффективности применения представленного выше простого ГА для минимизации информации (1-я из задач, сформулированных в лекции 4) при поиске маски приведены в табл. 30.1 (эти результаты получены на случайных исходных данных).

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

В процессе проведения расчетов было эмпирически установлено, что численность популяции достаточно ограничить 50 особями, а длину жизненного цикла - 50 поколениями.

В табл. 30.2 для сравнения приведены результаты решения той же задачи поиска оптимальной маски методом полного перебора.

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

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

Напомним, что данные, приведенные в табл. 30.3, были получены с применением специальных операторов булева кроссовера и мутации. При такой организации выполнения скрещивания и мутации в каждом новом поколении присутствуют особи с одним и тем же числом единиц в представляющих их хромосомах, т. е. особи-маски одного и того же объема. В связи с этим для решения задачи оптимизации информации вместо фитнес-функции (29.4) выгодно использовать фитнес-функцию (29.5), для которой ПГА должен найти минимум. Такое упрощение приводит к сокращению времени работы алгоритма.

Попытки находить решение 2-ой задачи методом полного перебора показали, что здесь ситуация полностью аналогична той, что имела место для 1-ой задачи. Для реальных задач поиска маски при длине полной реакции ДУ более 100 бит метод простого перебора практически не применим.

Приведем данные для сокращения ДИ конкретных реальных устройств. В следующей серии экспериментов была использована ДИ, полученная для ЦУ из каталога ISCAS'89 [2] при моделировании одиночных неисправностей с помощью вероятностных последовательностей в качестве диагностического теста. Каждый вероятностный тест был составлен из 100 входных наборов. В множество технических состояний для ДУ было включено исправное состояние, а также по одному представителю от каждого множества неотличимых друг от друга с помощью этого теста неисправностей.

Табл. 30.4 представляет динамику нахождения решения задачи минимизации ДИ для ЦУ из набора схем каталога ISCAS'89.

Данные, приведенные в этой таблице, так же как и в табл. 30.1, получены с применением выбора линейным ранжированием, оператора однородного кроссовера и фитнес-функции (4.1).

Табл. 30.5 показывает динамику нахождения решения задачи 2 для некоторых схем из набора ISCAS'89.

Так же как и в табл. 30.3 эти данные получены с применением специальных операторов кроссовера и мутации и фитнес-функции (29.4).

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

Эксперименты по нахождению индивидуальных масок проводились для ДИ полученной для ДУ из каталога ISCAS'89 при моделировании одиночных неисправностей с помощью тестовых последовательностей HITEC[3]. Так же как и в предыдущем случае в множество технических состояний было включено по одному представителю от каждого класса эквивалентности на множестве всевозможных технических состояний.