или gpgpgpu.
Генетические алгоритмы на GPU
Вкратце о том, как реализовать ГА на gpu.
При реализации на CPU у нас есть M хромосом (или популяция), в каждой из которой N ген.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhWNsqx73HjRMofgFl96eNkhY2DRa2G9uD_N-HkdZkD-0k5PDXMJn_WU436Qog5xsaFsSguqSZJEaV8tkfko_vqJxl2y-DgR8exbWk_2K65SCSIm3Jd5s6dyuzE3lt2XHBMsKJV1GKYKEV9/s320/1.PNG)
При реализации на GPU популяция представляется в виде множества потоков (текстур), где каждый элемент потока (rgba, в зависимости от формата текстуры) является отдельным геном(или 4, если rgba). Количество потоков равно количеству ген в хромосоме, а количество генов в одном потоке определяет размер популяции. Т.е. получаем 3д сетку вида:
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6PtKq1WDCDI5wQh86IxlZ-dJzySazXZPW_Y7EugxbvExgeRGvC39Y6pMK_I1W1ynJUpHIMzxsMP-ll-cM_psNw5XJvJw1j6kOptspD5M0psWDmRJzToNev3KwiGBEpPJtVcFXK7xSPkGF/s320/2.PNG)
Данное представление позволяет эффективно реализовать операторы скрещивания, мутации и замещения. Основными плюсами является то, что для каждого элемента потока (гена) требуется выборка только k ближайших соседей, что эффективно использует текстурный кеш видеокарты. Кроме того, можно упаковать и обработать до 4 ген(float) в одном элементе потока.
Если целевую функцию довольно просто посчитать в kernel, то удается избежать медленную передачу данных из GPU в CPU, поскольку тогда все данные (значения фитнеса) хранятся в видеопамяти. В противном случае необходимо оценить затраты на чтение/запись значений фитнеса, посчитанного на CPU и передаваемого на GPU, поскольку время записи/чтения может превысить весь суммарный эффект от распараллеливания.
Оператор скрещивания. На входе элемент потока и информация о k( на рисунке 4 соседа) соседях слева, справа, вверху, внизу. На выходе элемент потока.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjvzmNmnZegzMwbh_VZsVVdAwKvxJRUCUqyR8vQZWFFsnraUgSDY9Wlytvsz7bP4d1VsLlepb0lcSeYTzspzGtHFkD77sEKGMUkyYFnvnKjf0805ImfdhAYn42XOMpSP4SbsJt8TJvbgjZ2/s320/3.PNG)
С некоторой вероятностью скрещиваются две хромосомы, одна из которых является текущей, другая - с лучшим фитнесом среди k соседних. В результате скрещивания получается один потомок.
Оператор мутации. На входе/выходе элемент потока.
Любой оператор мутации реализуемый на CPU подойдет. Например, простейший для RCGA – добавление случайного числа из нормального распределения. В glsl коде это Rand текстура с этими значениями.
#extension GL_ARB_texture_rectangle : enable uniform sampler2DRect OldPopulation; uniform sampler2DRect Rand; uniform vec4 Up; uniform vec4 Down; void main() { vec4 cell = texture2DRect(OldPopulation, gl_TexCoord[0].st); vec4 rnd = texture2DRect(Rand, gl_TexCoord[1].st);
cell += rnd; gl_FragColor = clamp(cell, Up, Down); } |
_Winnie C++ Colorizer |
Оператор замещения. На входе поток с информацией о фитнессе, поток с популяцией до мутации и после. На выходе новая популяция.
Учитывая представление популяции и все входящие/исходящие потоки для каждого из операторов, общую схему работы генетического алгоритма можно описать следующим образом:
Параллельно для M хромосом выполнить:
1. Оператор скрещивания для N потоков, где N – количество генов.
2. Оператор мутации для N потоков. На выходе N новых потоков.
3. Подсчет фитнеса
4. Замещение
В реализации без CUDA, для шага 1,2,4 понадобится N проходов(render passes) и промежуточные текстуры для хранения результатов. Для шага 3 необходим всего один проход с информацией о всех N текстурах. Кроме того, необходима текстура со случайными числами, которая либо обновляется в каждой эпохе, либо выборка в mutation kernel происходит со случайных элементов (при этом значения остаются неизменными) потока этой текстуры. Такой случайный элемент задается с помощью случайных текстурных координат.
Такая реализация имеет следующее ограничения:
Количество потоков(текстур) ограничено.
Если функция фитнесса сложная, то может не хватить команд в kernel, тогда необходимо разбивать обработку потока на несколько kernels(или N проходов).
Позже код и дополнения.