{"id":496,"date":"2011-06-20T20:50:00","date_gmt":"2011-06-20T12:50:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=496"},"modified":"2023-11-02T20:52:20","modified_gmt":"2023-11-02T12:52:20","slug":"ga","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/496","title":{"rendered":"GA"},"content":{"rendered":"\n

GA(Genetic Algorithms)<\/strong>
GA\u7684\u61c9\u7528\u5305\u62ec,\u6392\u7a0b,\u6392\u5e8f,\u6d3e\u8eca\u554f\u984c(\u5148\u5206\u7fa4\u5728\u6392\u5e8f\u7684\u554f\u984c),\u7fa4\u7d44\u6280\u8853,\u5de5\u5ee0\u4f48\u7f6e,\u9078\u5740\u554f\u984c(\u8a2d\u9ede\u554f\u984c)
GA\u7684\u96a8\u6a5f\u641c\u5c0b\u6280\u8853\u662f\u5efa\u7acb\u5728\u4e00\u7a2e\u5929\u64c7\u7684\u6a5f\u5236 <\/p>\n\n\n\n

ps:
Evolutionary computation(\u6f14\u5316\u5f0f\u8a08\u7b97)<\/strong>
\u662f\u4e00\u7a2e\u96a8\u6a5f\u6700\u4f73\u5316\u6280\u8853
\u6a21\u64ec\u4eba\u985e\u81ea\u7136\u6f14\u5316\u904e\u7a0b,\u4ee5\u89e3\u6c7a\u56f0\u96e3\u554f\u984c,\u4e5f\u5c31\u662fNP-HARD(ex:2^n,\u5206\u7fa4)
\u5e38\u898b\u76843\u985e\u5982\u4e0b
GA(genetic algorithm) ,\u61c9\u7528\u6700\u5ee3
EP(evolutionary programming) \u7279\u6b8a\u72c0\u6cc1\u6642\u53ef\u7528
ESs(evolution strategies) <\/p>\n\n\n\n

GA term<\/strong>
population(\u6bcd\u9ad4):\u67d3\u8272\u9ad4\u7684\u96c6\u5408
chromosome(\u67d3\u8272\u9ad4):binary bit string,\u5c31\u662f\u4e00\u500bsolution(\u89e3)
genes(\u57fa\u56e0):bits,\u5c31\u662f\u89e3\u7684\u4e00\u90e8\u4efd
generation(\u4e16\u4ee3):\u5728\u6f14\u7b97\u6cd5\u4e2d\u662f\u4e00\u500b\u8ff4\u5708
fitness(\u9069\u61c9\u503c):\u503c\u8f03\u9ad8\u88ab\u6311\u4e2d\u7684\u6a5f\u7387\u5c31\u9ad8
offspring(\u5b50\u4ee3):\u65b0\u7684chromosome,\u4e5f\u5c31\u662fchromosome\u7684\u5f8c\u4ee3
crossover(\u4ea4\u914d):\u75312\u500bchromosome\u7522\u751foffspring\u7684\u52d5\u4f5c
mutation(\u7a81\u8b8a):chromosome\u7522\u751foffspring\u6642\u88ab\u6539\u8b8a
phenotype:\u89e3\u78bc\u5f8c\u7684\u5167\u5bb9solution
genotype:\u7de8\u78bc\u5f8c\u7684\u5167\u5bb9,\u4e5f\u5c31\u662fchromosome<\/p>\n\n\n\n

…………………………………<\/p>\n\n\n\n

GA\u6b65\u9a5f\u5927\u81f4\u5982\u4e0b
1
encoding(soluation)->population=many chromosomes<\/strong>
\u5c07\u771f\u5be6\u4e16\u754c\u7684\u8cc7\u6599\u7de8\u78bc\u6210\u591a\u500bbinary bit string,\u4e5f\u5c31\u662f\u591a\u500b\u67d3\u8272\u9ad4,\u5c31\u6703\u5f62\u6210\u4e00\u500b\u6bcd\u9ad4
2
(crossover(chromosomes_x,chromosomes_y) or mutation(chromosomes_z))->offspring<\/strong>
\u900f\u904e\u4ea4\u914d\u5c072\u500b\u4f4d\u5143\u5b57\u4e32\u5408\u6210\u70ba\u65b0\u7684\u4f4d\u5143\u5b57\u4e32
\u6216\u662f\u5c07\u4e00\u500b\u4f4d\u5143\u5b57\u4e32\u7a81\u8b8a\u6210\u53e6\u4e00\u500b\u65b0\u7684\u4f4d\u5143\u5b57\u4e32
\u6b64\u65b0\u7684\u4f4d\u5143\u5b57\u4e32\u4e5f\u5c31\u662f\u5b50\u4ee3
ps:\u9019\u908a\u662f\u76f2\u76ee\u64cd\u4f5c,\u5b8c\u5168\u4e0d\u7ba1\u771f\u5be6\u4e16\u754c\u7684\u8cc7\u6599
3
evaluate(decoding(offspring)) -> phenotype<\/strong>
\u5c07\u5b50\u4ee3\u89e3\u78bc\u4e26\u900f\u904e\u9069\u61c9\u6027\u8a08\u7b97\u53d6\u5f97\u89e3\u78bc\u5f8c\u7684\u5167\u5bb9
\u89e3\u78bc\u5167\u5bb9\u6703\u67093\u7a2e\u985e\u578b:illegal one(\u4e0d\u5408\u6cd5\u7684),infeasible one(\u4e0d\u53ef\u884c\u89e3)
4
selection(phenotype)-> new population=many chromosomes<\/strong>
\u5728\u900f\u904e\u5929\u64c7\u6311\u9078\u6210\u70ba\u65b0\u7684\u6bcd\u9ad4
5
\u91cd\u89862-4\u6b65\u9a5f\u76f4\u5230\u5f97\u5230\u6700\u4f73\u89e3<\/p>\n\n\n\n

ps:
selection\u901a\u5e38\u67092\u7a2e\u505a\u6cd5
regular sampling space<\/strong>:offspring\u7522\u751f\u5f8c\u6703\u53d6\u4ee3population\u5167\u90e8\u4efdchromosome,\u5728\u9032\u884c\u5929\u64c7
enlarged sampling space<\/strong>:offspring\u7522\u751f\u5f8c\u6703\u9644\u52a0\u5728parent\u5f8c,\u5728\u9032\u884c\u5929\u64c7,\u5be6\u4f5c\u8f03\u6613<\/p>\n\n\n\n

\u865b\u64ec\u78bc\u5982\u4e0b
\u8a2dP(t)\u70baparents,C(t)\u70ba\u73fe\u5728t\u4e16\u4ee3\u7684\u5b50\u4ee3<\/p>\n\n\n\n

Begin\n\u3000t = 0;\n\u3000initialize P(t); \/\/\u7522\u751fpopulation\n\u3000evaluate P(t);\n\u3000While (not termination condition) do \/\/\u9019\u88e1\u7684\u8ff4\u5708\u662f\u6307generation\n\u3000\u3000recombine P(t) to yield C(t);\u3000\u3000\u3000\/\/crossover or mutation\n\u3000\u3000evaluate C(t); \/\/decoding offspring\n\u3000\u3000select P(t+1) from P(t) and C(t); \/\/\u5929\u64c7\u5f62\u6210new population\n\u3000\u3000t = t + 1;\n\u3000End\nEnd<\/code><\/pre>\n\n\n\n
……………………………………..<\/p>\n\n\n\n
crossover operator(\u4ea4\u914d)<\/strong>
\u4ea4\u914d\u7387\u9ad8\u5247\u6703\u63a2\u7d22\u66f4\u591a\u89e3\u7a7a\u9593,\u6703\u56e0\u5047\u7684\u6700\u4f73\u89e3\u800c\u6e1b\u5c11\u5b89\u5b9a\u7684\u6a5f\u6703,\u800c\u4e14\u6703\u589e\u52a0\u8a08\u6642\u9593
\u4ea4\u914d\u65b9\u5f0f\u6709:\u55ae\u9ede,\u5169\u9ede,\u591a\u9ede,\u5747\u4e00
\u4ea4\u914d\u7387\u5efa\u8b70\u53c3\u6578:\u9ad8
\u4ea4\u914d\u7387\u5efa\u8b70\u4f7f\u7528\u6642\u9593:\u6f14\u5316\u665a\u671f
ps:\u63a2\u7d22\u4e0d\u5920\u5927,\u5bb9\u6613\u9677\u5165\u5340\u57df\u6700\u4f73\u89e3<\/p>\n\n\n\n
mutation operator(\u7a81\u8b8a)<\/strong>
\u7528\u9014:
1\u900f\u904e\u7a81\u8b8a\u88dc\u6551\u56de\u4f86\u4e4b\u524d\u5f9e\u6bcd\u9ad4\u907a\u5931\u7684\u57fa\u56e0
2\u6bcd\u9ad4\u539f\u672c\u6c92\u6709\u8b93\u57fa\u56e0,\u900f\u904e\u7a81\u8b8a\u8b8a\u51fa\u4f86
\u7a81\u8b8a\u7387\u592a\u4f4e:
1\u5f88\u591a\u57fa\u56e0\u7121\u6cd5\u88ab\u5617\u8a66
\u7a81\u8b8a\u7387\u592a\u9ad8:
1\u6703\u6709\u5e72\u64fe,\u53ef\u80fd\u6703\u5c07\u597d\u7684\u67d3\u8272\u9ad4\u8b8a\u6210\u58de\u7684\u67d3\u8272\u9ad4
2\u4ee3\u8207\u4ee3\u4e4b\u9593\u5931\u53bb\u76f8\u4f3c\u6027,\u627f\u8972\u80fd\u529b\u55aa\u5931
3\u6f14\u7b97\u6cd5\u6703\u5931\u53bb\u6b77\u53f2\u5b78\u7fd2\u80fd\u529b
\u7a81\u8b8a\u7387\u5efa\u8b70\u53c3\u6578:\u4f4e
\u7a81\u8b8a\u7387\u5efa\u8b70\u4f7f\u7528\u6642\u9593:\u6f14\u5316\u65e9\u671f<\/p>\n\n\n\n
……………..<\/p>\n\n\n\n
GA search\u7279\u8272:<\/strong>
1\u904b\u4f5c\u5728coding sapce\u89e3\u7a7a\u9593
2\u5f9e\u4e00\u7fa4\u89e3\u4e2dsearch,\u800c\u975e\u55ae\u4e00\u89e3search
3\u4f7f\u7528\u734e\u8cde\u6a5f\u5236,\u4e5f\u5c31\u662ffitness(\u9069\u61c9\u503c)\u4f86\u5c0e\u5f15\u5230\u6700\u4f73\u89e3,\u4e5f\u5c31\u662f\u53ea\u6709\u597d\u7684\u89e3\u6709\u9ad8\u6a5f\u7387\u7559\u4e0b\u4f86
4\u4f7f\u7528probabilistic transition rule(\u6982\u7387\u904e\u5ea6\u898f\u5247),\u800c\u975edeterministic rules<\/p>\n\n\n\n
GA search\u4f7f\u7528\u7684\u6280\u8853<\/strong>
ga\u4f7f\u7528fitness\u505a\u5c0e\u5f15,\u4e26\u7528crossover\u548cmutation\u96a8\u6a5f\u641c\u5c0b,\u5e73\u8861\u641c\u5c0b\u7a7a\u9593\u4e2d\u7684exploitation\u548cexploration<\/p>\n\n\n\n
1.exploitation(\u958b\u767c)<\/strong>
\u4e3b\u8981\u7528\u65bc\u6539\u5584\u73fe\u6709\u7684\u89e3
\u9069\u7528\u65bc\u6f14\u5316\u65e9\u671f,\u53calocal search<\/p>\n\n\n\n
2.exploration(\u63a2\u7d22)<\/strong>
\u4e3b\u8981\u7528\u65bc\u5c0b\u627e\u65b0\u7684\u89e3
\u9069\u7528\u65bc\u6f14\u5316\u665a\u671f,\u53cagobal search<\/p>\n\n\n\n
ps:\u641c\u5c0b\u7b56\u7565\u6709
blind strategies(\u76f2\u76ee\u7b56\u7565)
heuristic strategies(\u555f\u767c\u5f0f\u7b56\u7565)<\/p>\n\n\n\n
3.population-based search<\/strong>
\u7528\u591a\u884c\u7a0b\u57f7\u884csearch
\u50b3\u7d71search\u4f7f\u7528\u9ede\u5c0d\u9ede\u65b9\u5f0f,\u5bb9\u6613\u9677\u5165\u5340\u57df\u6700\u4f73\u89e3
GA\u4f7f\u7528population-based search\u53ef\u907f\u514d\u9019\u500b\u554f\u984c<\/p>\n\n\n\n
…………………………..<\/p>\n\n\n\n
\u7522\u751fpopulation<\/strong>
\u4ee5\u6700\u4f73\u5316\u554f\u984c\u70ba\u4f8b,\u5c07\u6c7a\u7b56\u8b8a\u6578\u7de8\u78bc\u4e26\u5f62\u6210\u6bcd\u9ad4
\u8a2d\u591a\u9805\u5f0fj\u70baa<=x<=b,
\u6b65\u9a5f\u5982\u4e0b
1\u5f9e2^(m-1) < (b-a)*10^4 <=2^m-1 \u6c42\u5f97m,\u4e5f\u5c31\u662f\u7de8\u78bc\u7684bit\u7bc4\u570d<\/strong>
ps:10^4\u662f\u81ea\u8a02\u7684
2\u6839\u64dam\u7684\u7bc4\u570d\u96a8\u6a5f\u7522\u751f\u4e0d\u540cbit\u7d44\u5408\u7684substring<\/strong>
ps:\u82e5\u8981\u89e3\u78bc\u53ef\u7528\u516c\u5f0f:x=a+decimal(substring)*(b-a)\/(2^m-1)
3\u5c07\u591a\u500bsubstring\u5408\u5728\u4e00\u8d77\u5f62\u6210\u4e00\u500bchromosome<\/strong>
4\u91cd\u89862-3\u6b65\u9a5f\u7522\u751f\u591a\u500bchromosome\u5f62\u6210\u6bcd\u9ad4<\/strong><\/p>\n\n\n\n
ex:
\u8a2d\u4ee5\u4e0b\u76ee\u6a19\u51fd\u5f0f
f(x1,x2)=max
\u53ca\u4ee5\u4e0b\u591a\u9805\u5f0f
-3 <= x1 <= 12.1
4.1 <= x2 <= 5.8
population\u7522\u751f\u6b65\u9a5f\u5982\u4e0b
1
\u5f9e2^(m-1) < (b-a)*10^4 <=2^m-1 \u6c42\u5f97m<\/strong>
\u5f9e\u591a\u9805\u5f0f1\u6c42m1
2^17 < 12.1-(-3)*10^4 <= 2^18
2^17 < 151000 <= 2^18
m1=18
\u5f9e\u591a\u9805\u5f0f2\u6c42m2
2^14 < (5.8-4.1)*10^4 <= 2^15
2^14 < 17000 <= 2^15
m2=15
2
\u6839\u64dam\u7684\u7bc4\u570d\u96a8\u6a5f\u7522\u751f\u4e0d\u540cbit\u7d44\u5408\u7684substring<\/strong>
\u56e0m1=18,\u96a8\u6a5f\u7522\u751f\u4e00\u7d44substring1
ex:000001010100101001
\u56e0m2=15,\u96a8\u6a5f\u7522\u751f\u4e00\u7d44substring2
ex:101111011111110
ps:
\u82e5\u8981\u89e3\u78bc\u53ef\u7528\u4ee5\u4e0b\u516c\u5f0f
x=a+decimal(substring)*(b-a)\/(2^m-1)<\/strong>
substring1\u89e3\u78bc
=-3+decimal(000001010100101001)*(12.1-(-3))\/(2^18-1)
=-3+5417*(12.1-(-3))\/(2^18-1)=-2.687969
substring2\u89e3\u78bc
=4.1+decimal(101111011111110)*(5.8-4.1)\/(2^15-1)
=4.1+24318*(5.8-4.1)\/(2^15-1)=5.361653
3
\u5c07\u591a\u500bsubstring\u5408\u5728\u4e00\u8d77\u5f62\u6210\u4e00\u500bchromosome<\/strong>
chromosome=substring1+substring2
000001010100101001101111011111110
4
\u91cd\u89862-3\u6b65\u9a5f\u7522\u751f\u591a\u500bchromosome\u5f62\u6210population<\/strong>
\u5047\u8a2d\u8a72\u6bcd\u9ad4\u53ea\u670910\u500bchromosome,\u7522\u751f\u4ee5\u4e0b10\u500b
v1=000001010100101001 101111011111110
v2=001110101110011000 000010101001000
v3=111000111000001000 010101001000110
v4=100110110100101101 000000001011101
v5=000010111101100010 001110001101000
v6=111110101011011000 000010110011001
v7=110100010011111000 100110011101101
v8=001011010100001100 010110011001100
v9=111110001011101100 011101000111101
v10=111101001110101010 000010101101010<\/p>\n\n\n\n
…………………………<\/p>\n\n\n\n
\u5f9epopulation\u89e3\u78bc\u5230\u5929\u64c7<\/strong>
\u6b65\u9a5f\u5982\u4e0b
1
decoding and evaluate<\/strong>
1.1\u5c07population\u4e2d\u7684chromosome decoding\u6210\u771f\u5be6\u4e16\u754c\u7684\u8cc7\u6599
1.2\u5c07\u5404\u8cc7\u6599\u653e\u5165\u76ee\u6a19\u51fd\u6578\u53d6\u5f97\u9069\u61c9\u503c,\u4ee5\u4e0b\u70ba\u5404chromosome\u9069\u61c9\u503c
2
selection<\/strong>
2.1\u5148\u5c07\u5404chromosome\u9069\u61c9\u503c\u8f49\u63db\u6210\u4ecb\u65bc0~1\u4e4b\u9593\u7684\u6bd4\u7387
2.2\u4f9d\u9069\u61c9\u503c\u767e\u5206\u6bd4\u5206\u914d\u5728\u4e00\u689d\u7dda\u4e0a
2.3\u6839\u64da\u8f2a\u76e4\u6cd5\u96a8\u6a5f\u7522\u751f10\u500b\u4ecb\u65bc0-1\u7684\u6578\u5b57,\u4e26\u4f9d\u6578\u5b57\u9078\u53d6\u65b0\u7684chromosome
ps:
\u4e4b\u5f8c\u9700\u9032\u884c\u4ee5\u4e0b\u6b65\u9a5f
crossover<\/strong>
\u8a2d\u5b9acrossover\u7387\u70baPc,ex:0.25
\u5728\u6839\u64daPc\u503c\u96a8\u6a5f\u5f9e\u6bcd\u9ad4\u4e2d\u6311\u9078n\u500b1\u5c0dchromosome\u9032\u884ccrossover
\u5047\u82e5\u6311\u9078chromosome\u6578\u91cf\u70ba\u5947\u6578,\u5247\u5c07\u5176\u4e2d\u4e00\u500b\u522a\u9664,\u6216\u662f\u5728\u6311\u9078\u4e00\u500bchromosome\u505acrossover
mutation<\/strong>
\u8a2d\u5b9amutation\u7387\u70baPm,ex:0.01
\u5728\u6839\u64daPm\u96a8\u6a5f\u5f9e\u6bcd\u9ad4\u4e2d\u6311\u9078chromosome\u9032\u884cmutation<\/p>\n\n\n\n
ex
\u4ee5\u4e0a\u8ff0\u6700\u4f73\u5316\u7bc4\u4f8b\u70ba\u4f8b,\u6b65\u9a5f\u5982\u4e0b
1
decoding and evaluate
1.1\u5c07population\u4e2d\u7684chromosome decoding\u6210\u771f\u5be6\u4e16\u754c\u7684\u8cc7\u6599<\/strong>
v1=(-2.687968,5.361653)
v2=(0.474101,4.170144)
V3=(10.419457,4.661461)
V4=(6.159951,4.109598)
V5=(-2.301286,4.477282)
V6=(11.788084,4.174346)
V7=(9.342067,5.121702)
V8=(-0.330256,4.694977)
V9=(11.671267,4.873501)
V10=(11.446273,4.171908)
1.2\u5c07\u5404\u8cc7\u6599\u653e\u5165\u76ee\u6a19\u51fd\u6578\u53d6\u5f97\u9069\u61c9\u503c,\u4ee5\u4e0b\u70ba\u5404chromosome\u9069\u61c9\u503c<\/strong>
eval(V1)=f(-2.687969,5.361653)=19.805119
eval(V2)=f(0.474101,4.170144)=17.370896
eval(V3)=f(10.419457,4.661461)=9.590546
eval(V4)=f(6.159951,4.109598)=29.406122
eval(V5)=f(-2.301286,4.477282)=15.68091
eval(V6)=f(11.788084,4.477282)=11.900541
eval(V7)=f(9.342067,5.121702)=17.958717
eval(V8)=f(-0.330256,4.694977)=19.763190
eval(V9)=f(11.671267,4.873501)=26.401669
eval(V10)=f(11.446273,4.171908)=10.252480
2
selection<\/strong>
2.1\u5148\u5c07\u5404chromosome\u9069\u61c9\u503c\u8f49\u63db\u6210\u4ecb\u65bc0~1\u4e4b\u9593\u7684\u6bd4\u7387
p1=0.111180
p2=0.097515
p3=0.053839
P4=0.165077
p5=0.088057
p6=0.066806
P7=0.100815
p8=0.11.945
p9=0.148211
P10=0.057554
2.2\u4f9d\u9069\u61c9\u503c\u767e\u5206\u6bd4\u5206\u914d\u5728\u4e00\u689d\u7dda\u4e0a
q1=0.111180
q2=0.208695
q3=0.262534
q4=0.427611
q5=0.515668
q6=0.582475
q7=0.683290
q8=0.794234
q9=0.942446
q10=1.000000
2.3\u6839\u64da\u8f2a\u76e4\u6cd5\u96a8\u6a5f\u7522\u751f10\u500b\u4ecb\u65bc0-1\u7684\u6578\u5b57,\u4e26\u4f9d\u6578\u5b57\u9078\u53d6\u65b0\u7684chromosome
0.301431(v4)
0.322062(v4)
0.766503(v8)
0.881893(v9)
0.350871(v4)
0.583392(v7)
0.177618(v2)
0.343242(v4)
0.343242(v1)
0.197577(v2)
\u56e0\u6b64\u65b0\u7684population\u70ba
v1=\u4e0a\u4e00\u4ee3v4=100110110100101101 000000001011101
v2=\u4e0a\u4e00\u4ee3v4=100110110100101101 000000001011101
v3=\u4e0a\u4e00\u4ee3v8=001011010100001100 010110011001100
v4=\u4e0a\u4e00\u4ee3v9=111110001011101100 011101000111101
v5=\u4e0a\u4e00\u4ee3v4=100110110100101101 000000001011101
v6=\u4e0a\u4e00\u4ee3v7=110100010011111000 100110011101101
v7=\u4e0a\u4e00\u4ee3v2=001110101110011000 000010101001000
v8=\u4e0a\u4e00\u4ee3v4=100110110100101101 000000001011101
v9=\u4e0a\u4e00\u4ee3v1=000001010100101001 101111011111110
v10=\u4e0a\u4e00\u4ee3v2=001110101110011000 000010101001000<\/p>\n\n\n\n
…………………………………..<\/p>\n\n\n\n
simple ga example in php(beta)<\/strong>
\u4ee5\u89e3\u8a72\u554f\u984c\u70ba\u4f8b
maxf(x1,x2)=21.5+x1sin(4pi*x1)+x2sin(20pi*x2)
-3.0\u2264x1\u226412.1
4.1\u2264 x2\u22645.8<\/p>\n\n\n\n
\/\/scripts as follows<\/p>\n\n\n\n
$limit=1000;\n$pm=0.25;\n$pc=0.5;\n\nif(is_numeric($_GET['limit'])){$limit=$_GET['limit'];}\nif(is_numeric($_GET['pc'])){$pc=$_GET['pc'];}\nif(is_numeric($_GET['pm'])){$pm=$_GET['pm'];}\n\nif($limit>5000)$limit=5000;\nif($pc>=1)$pc=0.99;\nif($pm>=1)$pm=0.99;\necho 'limit generation:'.$limit.' pc:'.$pc.' pm:'.$pm.'\n\n';\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\n$count=10;\necho $count.'statistic< br>';\nfor($i=1;$i<=$count;$i++){\n$result[]=ga($limit,$pc,$pm,$info);\n}\ncalresult($result);\n\necho '< br>The results of the implementation of 1 ga< br>';\nga($limit,$pc,$pm,$info);\ngraph($info['allmax']);\nprint_r($info['allmax']);\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction ga($limit,$pc,$pm,&$info){\n$info=NULL;\ninitialize($v);\nwhile($t<$limit){\ncrossover($v,$pc);\nmutation($v,$pm);\nevaluate($v);\nselect($v,$info);\n$t++;\n}\nreturn $info['max'];\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction calresult(&$data){\n$count=count($data);\nfor($i=0;$i<$count;$i++){\n$result=$data[$i];\nif($max<$result)$max=$result;\nif($min>$result || $min==null)$min=$result;\n$sum+=$result;\n}\n$avg=$sum\/$count;\n\nfor($i=1;$i<=$count;$i++){\n$std+=pow($data[$i]-$avg,2);\n}\n$std=sqrt($std\/$count);\n\necho '\nmax='.$max.'< br>\nmin='.$min.'< br>\navg='.$avg.'< br>\nstd='.$std.'< br>\n';\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction select(&$v,&$info){\n$p_size=10;\n$v_count=count($v);\n$info['max']=0;\n$info['t']++;\n\nfor($i=1;$i<=$p_size;$i++){\n$rand=rand(0,10000)\/10000;\nfor($j=1;$j<=$v_count;$j++){\nif($rand > $v[$j-1]['rateend'] && $rand <=$v[$j]['rateend']){\n\/\/echo $v[$j-1]['rateend'].'<'.$rand.'<'.$v[$j]['rateend'].\"n\";\n$new_v[$i]=$v[$j];\n}\n}\nif($info['max']<$new_v[$i]['fitness'])$info['max']=$new_v[$i]['fitness'];\n}\n$v=$new_v;\n$info['allmax'][]=$info['max'];\n\n\/*\nif($info['best']<$info['max']){\n$info['best']=$info['max'];\n$info['best_t']=$info['t'];\n}\nif($info['worst']==0){$info['worst']=$info['max'];}\nif($info['worst']>$info['max']){\n$info['worst']=$info['max'];\n$info['worst_t']=$info['t'];\n}\n*\/\n\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction mutation(&$v,$pm){\n$pm*=100;\n$v_count=10;\n$all=33;\n\nfor($i=1;$i<=$v_count;$i++){\nfor($j=0;$j<$all;$j++){\nif(rand(0,100)<$pm){\n$mutate=1;\n$gene=substr($v[$i]['chro'],$j,1);\nif($gene=='0')$v_new[$i]['chro']=substr_replace($v[$i]['chro'], '1',$j,1);\nif($gene=='1')$v_new[$i]['chro']=substr_replace($v[$i]['chro'], '0',$j,1);\n}\n}\nif($mutate==1){\n$mutate=0;\n$v[]['chro']=$v_new[$i]['chro'];\n}\n}\n\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction mutation2(&$v,$pm){\n$pm*=100;\n$v_count=count($v);\n$all=33;\n$cut=rand(0,$all);\n\nfor($i=1;$i<=$v_count;$i++){\nif(rand(0,100)<$pm){\n$gene=substr($v[$i]['chro'],$cut,1);\nif($gene=='0')$offspring=substr_replace($v[$i]['chro'], '1',$cut,1);\nif($gene=='1')$offspring=substr_replace($v[$i]['chro'], '0',$cut,1);\n$j++;\n$v[$v_count+$j]['chro']=$offspring;\n}\n}\n\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction crossover(&$v,$pc){\n$pc*=100;\n$v_count=count($v);\n$j=1;\nfor($i=1;$i<=$v_count;$i++){\nif(rand(0,100)<$pc){\n$parent[$j++]=$v[$i]['chro'];\n}\n}\n\n$p_count=count($parent);\n$all=35;\n$cut=rand(0,$all);\n\nfor($i=1;$i<$p_count;$i++){\n$parent_a1=substr($parent[$i],0,$cut);\n$parent_a2=substr($parent[$i],$cut,$all-$cut);\n$parent_b1=substr($parent[$i+1],0,$cut);\n$parent_b2=substr($parent[$i+1],$cut,$all-$cut);\n$offspring1=$parent_a1.$parent_b2;\n$offspring2=$parent_b1.$parent_a2;\n\n$v[$v_count+1]['chro']=$offspring1;\n$v[$v_count+2]['chro']=$offspring2;\n\n$i++;\n}\n\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction evaluate(&$v,&$max=null){\n$v_count=count($v);\nfor($i=1;$i<=$v_count;$i++){\n$x1=vdecode(substr($v[$i]['chro'],0,18),-3,12.1,18);\n$x2=vdecode(substr($v[$i]['chro'],18,15),4.1,5.8,15);\n$v[$i]['fitness']=maxfunction($x1,$x2);\n$fitnesstotal+=$v[$i]['fitness'];\nif($max<$v[$i]['fitness'])$max=$v[$i]['fitness'];\n}\n\nfor($i=1;$i<=$v_count;$i++){\n$v[$i]['rate']=$v[$i]['fitness']\/$fitnesstotal;\n$rate+=$v[$i]['rate'];\n$v[$i]['rateend']=$rate;\n}\n\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction maxfunction($x1,$x2){\n$pi=pi();\nreturn 21.5+$x1*sin(4*$pi*$x1)+$x2*sin(20*$pi*$x2);\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction vdecode($binary,$min,$max,$m){\n$x=$min+bindec($binary)*($max-($min))\/(pow(2,$m)-1);\nreturn $x;\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction initialize(&$v){\n\/*\n$min=-3;\n$max=12.1;\n$multiple=10000;\n$min*=$multiple;\n$max*=$multiple;\n$range=$max-$min;\n$offsend=rand(0,$range);\n$value=($min+$offsend)\/$multiple;\n*\/\n\n$p_size=10;\n$m1=18;\n$m2=15;\n$m=$m1+$m2;\n\nfor($j=1;$j<=$p_size;$j++){\nfor($i=1;$i<=$m;$i++){\n$v[$j]['chro'].=rand(0,1);\n}\n}\n\n\/\/print_r($v);\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction graph($data){\n$im = imagecreate(1100,370);\n$green = imagecolorallocate($im,214,235,214);\n$black = imagecolorallocate ($im, 0, 0, 0);\nimageline($im,10,300,1000,300, $black );\nimageline($im,10,5,10,300, $black );\nimagestring($im,3,1000,300,\"generation\",$black);\nimagestring($im,3,8,1,\"soluation\",$black);\n\n$x = 10;\n$y = 300;\n$count=count($data)-1;\nfor($i=0;$i<$count;$i++){\nimageline($im,$x+$i,450-$data[$i]*10,$x+$i+1,450-$data[$i+1]*10,$black);\n}\n\nfor ($i=0;$i<6;$i++){\nimagestring( $im,2,1,450-(20+$i*5)*10,20+$i*5,$black);\n}\nfor ($i=0;$i<=10;$i++){\nimagestring( $im,2,$x+$i*100,$y+11,$i*100,$black);\n}\n\nimagepng($im, \"a.png\");\necho \"< img src='a.png' >\";\nimagedestroy($im);\n\n}<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
GA(Genetic Algorithms)GA\u7684\u61c9\u7528\u5305\u62ec, …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[13],"tags":[],"class_list":["post-496","post","type-post","status-publish","format-standard","hentry","category-dataanalysis"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/496","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=496"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/496\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=496"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=496"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=496"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}