четверг, 8 мая 2008 г.

Норма по популяции

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

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

// Код на C

double inline pop_norm(double *pop,
int pop_cnt,
int gen_len)
{
double res = 0 ;
double mn, mx ;
double *p ;

for( i=0 ; i<gen_len ; i++ )
{
p = pop + i ;
mn = 1 ;
mx = 0 ;
for( j=0 ; j<pop_cnt ; j++,p+=gen_len )
{
if(*p > mx) mx = *p ;
if(*p < mn) mn = *p ;
}
res += mx - mn ;
}

return res/gen_len ;
}

среда, 7 мая 2008 г.

Кодирование списком

В данном представлении ген - это число из диапазона от 0 до 1, а параметр - это значение из списка некоторой длины.

// Код на С

#define Round(x) ((x)>=0?(long) ((x)+0.5):(long)((x)-0.5))

#define gen2par_list(gen,list,cnt) (list[gen2ind(gen,cnt)])

int inline gen2ind(double gen, int cnt)
{
int res ;
res = Round(gen*(cnt-1)) ;
res = (res>=(cnt-1)?cnt-1:res) ;
res = (res<0?0:res) ;
return res ;
}

Кодирование диапазоном

В данной кодировке ген - это число из диапазона от 0 до 1, а параметр - это число от нижней границы диапазона до верхней границы диапазона. Простое линейное преобразование.

par = (up - dn) * gen + dn


где: par - искомый параметр, up - верхняя граница диапазона, dn - нижняя граница диапазона.

// Код на С

#define gen2par_diap(gen,diap,dn) ( diap * gen + dn )
// diap = up - dn

Перемешивание

Индексы плохой и хорошей части популяции необходимо перемешать случайным образом.

// Код на SciLab

function ind = randperm(cnt)
[s,ind] = sort(rand(cnt,1)) ;
endfunction

gi = gi(randperm(length(gi))) ;
bi = gi(randperm(length(bi))) ;


// Код на C

void inline mix_ind(int *ind,int cnt)
{
int num,i,k ;

for(i=0;i<cnt;i++)
for(k=0;k<(cnt-1);k++)
if(rand_unf > 0.5)
{
num = ind[k+1] ;
ind[k+1] = ind[k] ;
ind[k] = num ;
}
}

Сортировка

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

 // Код на SciLab

function [gi,bi] = sort_pop(kach)
[s,ind] = sort(kach) ;
gi = ind(1:($/2)) ;
bi = ind(($/2+1):$) ;
endfunction


 // Код на C

void inline sort_pop(int pop_cnt,
int *pop_ind,
double *pop_kach)
{
int k,p,ind, pc1 ;
int *pi ;
pi = pop_ind ;

for( p=0 ; p<pop_cnt ; p++,pi++ )
*pi = p ;

pc1 = pop_cnt - 1 ;
for( p=0 ; p<pc1 ; p++ )
for( k=0 ; k<pc1 ; k++ )
#define IND(k) (pop_ind[k])
#define VAL(k) (pop_kach[IND(k)])
if(VAL(k)>VAL(k+1))
{
ind = IND(k+1) ;
IND(k+1) = IND(k) ;
IND(k) = ind ;
}
#undef IND
#undef VAL
}

Одна эпоха генетики

Полностью эпоха состоит из следующих этапов:


1. подготовка эпохи
2. расчет всех элементов популяции
- расшифровка геномов и создание объектов
- расчет объектов (симуляция деятельности объектов)
- расчет качества объектов
3. трансформация популяции
- сортировка
- нахождение лучшего
- ранжирование
- скрещивание
- мутация
- ограничение
4. завершение эпохи
- запись истории качества и параметров

Ограничение

В нашей модели значения генов могут быть в диапазоне от 0 до 1. Соответственно после преобразования популяции необходимо приводить их к этому диапазону, т.к. возможны варианты выхода за пределы. Ограничиваем просто - отрезаем лишнее.

Эту процедуру необходимо выполнить для всех новых геномов.

 // Код на С

void inline ogr(double *genom,
int gen_len)
{
for( ; 0<gen_len ; gen_len--,genom++ )
{
if((*genom) < 0) *genom = 0 ;
if((*genom) > 1) *genom = 1 ;
}
}

вторник, 6 мая 2008 г.

Мутация

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

gen = gen + (rand * 2 - 1) * μ


где: gen - текущий ген, rand - случайное число из диапазона 0...1 по равномерному закону, μ - коэффициент мутации.

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

if(rand < flash) mu *= 10 ;


где: flash - частота шока.

// Код на С

#define rand_unf ( (double)rand() / (double)RAND_MAX )

void inline mutate(double *genom,
int gen_len,
double mu,
double flash)
{
double mu10 ;

mu10 = mu * 10 ;

for( ; 0<gen_len ; gen_len--,genom++ )
if(rand_unf < flash)
*genom += (rand_unf*2-1) * mu10 ;
else
*genom += (rand_unf*2-1) * mu ;
}


// Код на SciLab

function genom = mutate(genom,mu,flash)
for i = 1:length(genom)
m = mu ;

if rand(1,1,"uniform") < flash
m = mu * 10 ;
end

genom(i) = genom(i) + (rand(1,1,"uniform")*2-1)*m ;
end
endfunction

Скрещивание

Имеем два хороших генома и два плохих.

Последовательно движемся по генам плохих и хороших. Заполняем плохие геномы по одному из следующих правил:

1) bg1(i) = gg1(i) ; bg2(i) = gg2(i) ;

2) bg2(i) = gg1(i) ; bg1(i) = gg2(i) ;


где: bg1 и bg2 - плохие геномы, gg1 и gg2 - хорошие геномы.

Выбор осуществляем по случайному.

// Код на С

void inline xver(double *b1,
double *b2,
double *g1,
double *g2,
int cnt)
{


for(;0<cnt;cnt--,b1++,b2++,g1++,g2++)
if(rand_unf > 0.5)
{
*b1 = *g1 ;
*b2 = *g2 ;
}
else
{
*b2 = *g1 ;
*b1 = *g2 ;
}
}

Трансформация популяции.

В конце каждой эпохи генетической оптимизации производим трансформацию популяции. Цель трансформации - передать дальше лучшие свойства.

Делаем в несколько этапов:

1. сортировка
2. перемешивание
3. скрещивание
4. мутирование
5. ограничение


// Код на С

void trans_pop(int pop_cnt,
int *pop_ind,
double *pop_kach,
int gen_len,
double *pop,
double mu,
double flash,
int *best_num)
{
int k, p , p2, p3 ;
double *b1,*b2 ;

sort_pop(pop_cnt,pop_ind,pop_kach) ;

*best_num = pop_ind[pop_cnt-1] ;

p = pop_cnt/2 ;
mix_ind(pop_ind,p) ;
mix_ind(pop_ind+p,p) ;

p = pop_cnt/4 ;
p2 = p * 2 ;
p3 = p * 3 ;

for( k=0 ; k<p ; k++ )
{
#define IND(k) (pop_ind[k])
#define GEN(k) (pop+IND(k)*gen_len)

b1 = GEN(k) ;
b2 = GEN(k+p) ;

xver(b1,b2,GEN(k+p2),GEN(k+p3),gen_len) ;

#undef IND
#undef GEN

mutate(b1,gen_len,mu,flash) ;
mutate(b2,gen_len,mu,flash) ;

ogr(b1,gen_len) ;
ogr(b2,gen_len) ;
}
}