Day 4: MFC stuff

2009-09-29T08:58:00.000-07:00

По умолчанию CListBox не умеет прокручивать по горизонтали. Для того чтобы обойти это ограничение, необходимо добавить код, который будет считать максмимальную длинну строк и через CListBox::SetHorizontalExtent сдвигать содержимое.

void UpdateHorizBarWidth( const CString & item )
{
CClientDC dc(this);

CFont * pFont = CListBox::GetFont();
dc.SelectObject(pFont);

CSize size = dc.GetTextExtent(item);
size.cx += 3 * ::GetSystemMetrics(SM_CXBORDER);

if( size.cx > MaxWidth )
{
MaxWidth = size.cx;
CListBox::SetHorizontalExtent(MaxWidth);
}
}

_Winnie C++ Colorizer

Ес-но придется вызывать foreach UpdateHorizBarWidth при каждом изменении данных ListBox.

Day 3: NN Crossover & Mutation

2009-06-09T11:25:00.000-07:00

Позавчера на #gamedev Suslik рассказывал про свое использование нейронных сетей и ГА.
http://www.gamedev.ru/flame/forum/?id=75030&page=45#m663
про скрещивание и мутацию нейронных сетей.
а вот совсем случайно наткнулся на такой способ:
для многослойного персептрона с прямым распространением этот процесс представляет собой образование новой нейронной сети, в которой выходные нейроны родителей станут скрытыми нейронами потомка. При этом сохраняются знания, накопленные родителями. и рисунок

с мутацией еще проще: веса сетки умножаются на случайное число.

Day 2: Genetics Algorithms On GPU

2009-05-27T04:08:00.000-07:00

или gpgpgpu.

Генетические алгоритмы на GPU

Вкратце о том, как реализовать ГА на gpu.
При реализации на CPU у нас есть M хромосом (или популяция), в каждой из которой N ген.

При реализации на GPU популяция представляется в виде множества потоков (текстур), где каждый элемент потока (rgba, в зависимости от формата текстуры) является отдельным геном(или 4, если rgba). Количество потоков равно количеству ген в хромосоме, а количество генов в одном потоке определяет размер популяции. Т.е. получаем 3д сетку вида:

Данное представление позволяет эффективно реализовать операторы скрещивания, мутации и замещения. Основными плюсами является то, что для каждого элемента потока (гена) требуется выборка только k ближайших соседей, что эффективно использует текстурный кеш видеокарты. Кроме того, можно упаковать и обработать до 4 ген(float) в одном элементе потока.
Если целевую функцию довольно просто посчитать в kernel, то удается избежать медленную передачу данных из GPU в CPU, поскольку тогда все данные (значения фитнеса) хранятся в видеопамяти. В противном случае необходимо оценить затраты на чтение/запись значений фитнеса, посчитанного на CPU и передаваемого на GPU, поскольку время записи/чтения может превысить весь суммарный эффект от распараллеливания.

Оператор скрещивания. На входе элемент потока и информация о k( на рисунке 4 соседа) соседях слева, справа, вверху, внизу. На выходе элемент потока.

С некоторой вероятностью скрещиваются две хромосомы, одна из которых является текущей, другая - с лучшим фитнесом среди 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 проходов).
Позже код и дополнения.

Day 1: Intro

2009-05-25T15:16:00.000-07:00

Буду писать о gamedev, эвристике, NP-задачах, вообщем тем, чем сейчас занимаюсь. Надеюсь это будет происходить часто и доступно.

Mengeengineering

Day 4: MFC stuff

Day 3: NN Crossover & Mutation

Day 2: Genetics Algorithms On GPU

Day 1: Intro