用erlang写的遗传算法

闲来无事，看遗传算法。于是用erlang写了个简单的小程序。x从0到15，求x的值，使f(x) = 15x-x*x的值最大。

产生8个个体，用f(x)的值作为适应度，然后排序，每个个体的累积概率为，自身适应度－最小适应度＋前一个的累积概率。为了提高高适应度被选中的概率，对其累积概率再取平方。每次根据累积概率随机取两个个体对其染色体做交叉，产生两个子代，取4次，便产生8个子代。如此反复，总共进化16代。大多数情况，很快就可以稳定了，没有做基因突变。

大多数情况都能取到7,8 附近，算是成功了吧，呵呵。

%% main.erl
-module(ga).

-export([
start/0
]).

%% Gene {Chromosome, Fitness, Acc_fit}
%% Acc_fit : Accumulation Fitness

%% start
start() ->
{A, B, C} = erlang:now(),
random:seed(A, B, C),
Gene = generate_original_gene([], 8),
evolve(Gene, 16, 0),
ok.

%% function
function(Chromosome) ->
<<X>> = Chromosome,
15*X-X*X.

%% generate_original_gene
generate_original_gene([], Count) ->
Chromosome = random:uniform(16),
Fitness = function(<<Chromosome>>),
generate_original_gene([{<<Chromosome>>, Fitness, 0}], Count-1);
generate_original_gene(Gene, 0) ->
acc_fitness(Gene);
generate_original_gene(Gene, Count) ->
Gene_new = get_gene(Gene),
generate_original_gene([Gene_new]++Gene, Count-1).

%% get_gene
get_gene(Gene) ->
Chromosome = random:uniform(16),
Fitness = function(<<Chromosome>>),
Find = lists:member({<<Chromosome>>, Fitness, 0}, Gene),
if
Find == true ->
get_gene(Gene);
true ->
{<<Chromosome>>, Fitness, 0}
end.

%% acc_fitness
acc_fitness(Gene) ->
io:fwrite("unsort : ~w~n", [Gene]),
Gene_sort = sort(Gene),
io:fwrite("sort : ~w~n", [Gene_sort]),
{_, Base, _} = lists:nth(1, Gene_sort),
acc_fitness(Gene_sort, [], -Base).
acc_fitness([Gene_0, Gene_1|Gene], [], Base) ->
{_, Fitness, _} = Gene_0,
{Chromosome_1, Fitness_1, _} = Gene_1,
Gene_1_new = {Chromosome_1, Fitness_1, Fitness_1+Base+Fitness},
acc_fitness([Gene_1_new]++Gene, [Gene_0], Base);
acc_fitness([Gene_0, Gene_1|Gene], Gene_acc, Base) ->
{_, _, Acc_fit_0} = Gene_0,
{Chromosome_1, Fitness_1, _} = Gene_1,
Gene_1_new = {Chromosome_1, Fitness_1, Fitness_1+Base+Acc_fit_0},
acc_fitness([Gene_1_new]++Gene, Gene_acc++[Gene_0], Base);
acc_fitness([Gene], Gene_acc, _) ->
%%Gene_acc_new = Gene_acc++[Gene],
%% to improve the probability of hight fitness.
Gene_acc_new = [{Chromosome, Fitness, Acc_fit*Acc_fit} || {Chromosome, Fitness, Acc_fit} <- Gene_acc++[Gene]],
io:fwrite("acc fitness : ~w~n", [Gene_acc_new]),
Gene_acc_new.

%% sort
sort(Gene) ->
lists:sort(fun callback_sort/2, Gene).

%% callback_sort
%% small defore big
callback_sort({_, Fitness_0, _}, {_, Fitness_1, _}) ->
if
Fitness_0 > Fitness_1 -> false;
true -> true
end.

%% crossover
crossover(Gene_0, Gene_1) ->
Pos = random:uniform(4),
if
Gene_0 == Gene_1 ->
io:fwrite("uncrossover~n"),
[Gene_0, Gene_1];
Pos == 0 ->
io:fwrite("uncrossover~n"),
[Gene_0, Gene_1];
true ->
crossover(Gene_0, Gene_1, Pos, 4-Pos)
end.
crossover(Gene_0, Gene_1, Pos_h, Pos_l) ->
{<<_:4, Chromosome_0_h:Pos_h, Chromosome_0_l:Pos_l>>, _, _} = Gene_0,
{<<_:4, Chromosome_1_h:Pos_h, Chromosome_1_l:Pos_l>>, _, _} = Gene_1,
Chromosome_0_child = <<0:4, Chromosome_0_h:Pos_h, Chromosome_1_l:Pos_l>>,
Chromosome_1_child = <<0:4, Chromosome_1_h:Pos_h, Chromosome_0_l:Pos_l>>,
Fitness_0_child = function(Chromosome_0_child),
Fitness_1_child = function(Chromosome_1_child),
Gene_0_child = {Chromosome_0_child, Fitness_0_child, 0},
Gene_1_child = {Chromosome_1_child, Fitness_1_child, 0},
io:fwrite("crossover : ~w~n", [[Gene_0_child, Gene_1_child]]),
[Gene_0_child, Gene_1_child].

%% select
select(Gene) ->
{_, _, Fitness_sum} = lists:last(Gene),
Select_fitness_0 = random:uniform(Fitness_sum),
{Select_0, Unselect_0} = select(Gene, [], Select_fitness_0),
Select_fitness_1 = random:uniform(Fitness_sum),
{Select_1, Unselect_1} = select(Unselect_0, [], Select_fitness_1),
io:fwrite("select : ~w~n", [{Select_0, Select_1, Unselect_1}]),
{Select_0, Select_1, Unselect_1}.
select([{Chromosome, Fitness, Acc_fit}|Gene], [], Select_fitness) ->
if
Select_fitness > Acc_fit ->
select(Gene, [{Chromosome, Fitness, Acc_fit}], Select_fitness);
true ->
{{Chromosome, Fitness, Acc_fit}, Gene}
end;
select([{Chromosome, Fitness, Acc_fit}], Unselect, _) ->
{{Chromosome, Fitness, Acc_fit}, Unselect};
select([{Chromosome, Fitness, Acc_fit}|Gene], Unselect, Select_fitness) ->
if
Select_fitness > Acc_fit ->
select(Gene, Unselect++[{Chromosome, Fitness, Acc_fit}], Select_fitness);
true ->
{{Chromosome, Fitness, Acc_fit}, Unselect++Gene}
end.

%% propagate
propagate(Gene, []) ->
propagate(Gene, [], -1).
propagate(Gene, [], -1) ->
Count = length(Gene) div 2,
propagate(Gene, [], Count);
propagate(_, Child_gene, 0) ->
acc_fitness(Child_gene);
propagate(Gene, [], Count) ->
{Select_0, Select_1, _} = select(Gene),
Select_child = crossover(Select_0, Select_1),
propagate(Gene, Select_child, Count-1);
propagate(Gene, Child_gene, Count) ->
{Select_0, Select_1, _} = select(Gene),
Select_child = crossover(Select_0, Select_1),
propagate(Gene, Select_child++Child_gene, Count-1).

%% evolve
evolve(_, 0, _) ->
ok;
evolve(Gene, Count, Generation) ->
io:fwrite("generation : ~w~n", [Generation+1]),
Child_gene = propagate(Gene, []),
evolve(Child_gene, Count-1, Generation+1).