Evolutionary algorithm: Difference between revisions
Added Easylang
(Added Easylang) |
|||
| (15 intermediate revisions by 9 users not shown) | |||
Line 685:
380: METHINKS ITBIS LIKE A WEASEL, fitness: 27
Final ( 384): METHINKS IT IS LIKE A WEASEL, fitness: 28</pre>
=={{header|ABC}}==
<syntaxhighlight lang="ABC">PUT "ABCDEFGHIJKLMNOPQRSTUVWXYZ " IN alphabet
HOW TO RETURN initial.state target:
SHARE alphabet
PUT "" IN state
FOR c IN target: PUT state^choice alphabet IN state
RETURN state
HOW TO RETURN state fitness target:
PUT #target IN score
FOR i IN {1..#target}:
IF state item i = target item i: PUT score-1 IN score
RETURN score
HOW TO RETURN chance mutate state:
SHARE alphabet
PUT "" IN mutated
FOR i IN {1..#state}:
SELECT:
random < chance: PUT choice alphabet IN next
ELSE: PUT state item i IN next
PUT mutated^next IN mutated
RETURN mutated
HOW TO EVOLVE TOWARD target:
PUT 0.1 IN mutation.rate
PUT 100 IN generation.size
PUT initial.state target IN state
WHILE state fitness target > 0:
WRITE (state fitness target)>>2, ": ", state/
PUT {} IN next.generation
FOR i IN {1..generation.size}:
PUT mutation.rate mutate state IN child
PUT child fitness target IN score
PUT child IN next.generation[score]
PUT next.generation[min keys next.generation] IN state
WRITE (state fitness target)>>2, ": ", state/
EVOLVE TOWARD "METHINKS IT IS LIKE A WEASEL"</syntaxhighlight>
{{out}}
<pre>27: CYPPYRQHMACPLQIZLPETRJVVPYLI
26: CYPPYRQHMICPLQIZLPEDRJVVPILI
25: CYKPYRQH ICPLWIZLPEDRJVJPILI
24: CWKPWWQH ICPLSIZLPEDRJVJPILI
23: CWKPWWQH ICPLSIZLPEDR BJPILI
21: CWKPWWQH ICPLSIZLSEDA BJA LI
20: JWKPWWKH ICPLSIZLSEDA BJA LK
19: WWKPIWKG ICPLSIZLSEDA BJA LK
18: WWKPIWKG ICPLSILLSEDA BJA LK
17: WWKPIWKG ICPLSILISEDA BJA LK
17: IWMPIWKG ICPLSILISEDA BJA LK
16: IWMPIWKG ICPLSILISEDA WJA LK
15: IWMPIWKG ICPLSILISEDA WEA LK
...
1: METHINKS IT IS LIKE A WEAS L
1: METHINKS IT IS LIKE A WEAS L
1: METHINKS IT IS LIKE A WEAS L
0: METHINKS IT IS LIKE A WEASEL</pre>
=={{header|Aime}}==
Line 788 ⟶ 848:
=={{header|ALGOL 68}}==
{{trans|C|but using a fixed mutation rate}} Note: This specimen retains the original [[#C|C]] coding style.
{{works with|ALGOL 68|Revision 1 - no extensions to language used.}}
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny].}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}
<syntaxhighlight lang="algol68">
STRING target := "METHINKS IT IS LIKE A WEASEL";
PROC fitness = (STRING tstrg)REAL:
Line 828 ⟶ 889:
INT iters := 0;
kid[LWB kid] := LOC[UPB target]CHAR;
REAL mutate rate = 0.05;
# initialize #
Line 836 ⟶ 897:
fits := fitness(parent);
WHILE
INT j;
REAL kf;
FOR j FROM LWB kid TO UPB kid DO
mutate(kid[j], parent, mutate rate)
Line 850 ⟶ 910:
FI
OD;
DO
kewe( parent, iters, fits, mutate rate );
iters+:=1
OD;
Line 861 ⟶ 921:
(
evolve
)
</syntaxhighlight>
Sample output:
<pre>
#0000 fitness: 0.00% 0.
#
#
#
#
#0005 fitness: 0.00% 0.0500 'QBJQGSQU LSIJP MHOO D MPYMFN'
#0006 fitness: 0.00% 0.0500 'QBJQGSQU LSIJP MHOO D MPCMFN'
#0007 fitness: 0.00% 0.0500 'QBRQGSQU LSIJP MHOO D MPCMFN'
#0008 fitness: 0.00% 0.0500 'QBRQGLQU LSIJP MHOE D MPCMFN'
...
#0097 fitness: 90.48% 0.0500 'METHIOKS IT IS LIKE A WEASEL'
#0098 fitness: 90.48% 0.0500 'METHIOKS IT IS LIKE A WEASEL'
#0099 fitness: 90.48% 0.0500 'METHIOKS IT IS LIKE A WEASEL'
#0100 fitness: 90.48% 0.0500 'METHIOKS IT IS LIKE A WEASEL'
#0101 fitness: 90.48% 0.0500 'METHIOKS IT IS LIKE A WEASEL'
#0102 fitness: 90.48% 0.0500 'METHIOKS IT IS LIKE A WEASEL'
#0103 fitness: 90.48% 0.0500 'METHIOKS IT IS LIKE A WEASEL'
#0104 fitness: 100.00% 0.0500 'METHINKS IT IS LIKE A WEASEL'
</pre>
Line 2,507 ⟶ 2,581:
Generation 23, dist= 1: METHINKS IT IS LIKE A WEASEW
Generation 24, dist= 0: METHINKS IT IS LIKE A WEASEL</pre>
=={{header|Dart}}==
{{trans|Java}}
<syntaxhighlight lang="Dart">
import 'dart:math';
class EvoAlgo {
static final String target = "METHINKS IT IS LIKE A WEASEL";
static final List<String> possibilities = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ".split('');
static int c = 100; // Number of spawn per generation
static double minMutateRate = 0.09;
static int perfectFitness = target.length;
static String parent = '';
static Random rand = Random();
static int fitness(String trial) {
int retVal = 0;
for (int i = 0; i < trial.length; i++) {
if (trial[i] == target[i]) retVal++;
}
return retVal;
}
static double newMutateRate() {
return (((perfectFitness - fitness(parent)) / perfectFitness) * (1 - minMutateRate));
}
static String mutate(String parent, double rate) {
String retVal = '';
for (int i = 0; i < parent.length; i++) {
retVal += (rand.nextDouble() <= rate)
? possibilities[rand.nextInt(possibilities.length)]
: parent[i];
}
return retVal;
}
static void main() {
parent = mutate(target, 1);
int iter = 0;
while (parent != target) {
double rate = newMutateRate();
iter++;
if (iter % 100 == 0) {
print('$iter: $parent, fitness: ${fitness(parent)}, rate: $rate');
}
String bestSpawn;
int bestFit = 0;
for (int i = 0; i < c; i++) {
String spawn = mutate(parent, rate);
int fit = fitness(spawn);
if (fit > bestFit) {
bestSpawn = spawn;
bestFit = fit;
}
}
if (bestFit > fitness(parent)) {
parent = bestSpawn;
}
}
print('$parent, $iter');
}
}
void main() {
EvoAlgo.main();
}
</syntaxhighlight>
{{out}}
<pre>
100: MFTHINFU IR N WLEKWKA WQZKYM, fitness: 13, rate: 0.4875
200: MXTHINPJ HR NNTLEKF A WDZHEH, fitness: 14, rate: 0.455
300: YNTHINPJ IK IS LEKNNA ADZHEL, fitness: 16, rate: 0.39
400: XETHI PS IKXIS LBKNDA QEUSEL, fitness: 18, rate: 0.325
500: NETHINPS I IS IBKLNA WEASEL, fitness: 21, rate: 0.2275
METHINKS IT IS LIKE A WEASEL, 551
</pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Evolutionary_algorithm#Pascal Pascal].
Line 2,555 ⟶ 2,708:
weasel()</syntaxhighlight>
=={{header|EasyLang}}==
<syntaxhighlight>
target$ = "METHINKS IT IS LIKE A WEASEL"
abc$[] = strchars " ABCDEFGHIJLKLMNOPQRSTUVWXYZ"
P = 0.05
C = 100
func fitness trial$ .
for i to len trial$
res += if substr trial$ i 1 <> substr target$ i 1
.
return res
.
func$ mutate parent$ .
for c$ in strchars parent$
if randomf < P
res$ &= abc$[randint len abc$[]]
else
res$ &= c$
.
.
return res$
.
for i to len target$
parent$ &= abc$[randint len abc$[]]
.
while fitness parent$ > 0
copies$[] = [ ]
for i to C
copies$[] &= mutate parent$
.
parent$ = copies$[1]
for s$ in copies$[]
if fitness s$ < fitness parent$
parent$ = s$
.
.
step += 1
print step & " " & parent$
.
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 2,632 ⟶ 2,826:
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">import system'routines;
import extensions;
Line 2,651 ⟶ 2,845:
{
randomString()
= 0.repeatTill(self).selectBy::(x => randomChar).summarize(new StringWriter());
fitnessOf(s)
Line 2,657 ⟶ 2,851:
mutate(p)
= self.selectBy::(ch => rnd.nextReal() <= p ? randomChar : ch).summarize(new StringWriter());
}
class EvoAlgorithm : Enumerator
{
object
object
object
constructor new(s,count)
{
}
get Value() =
bool next()
{
if (nil ==
{
if (
{ ^ false };
auto variants := Array.allocate(
^ true
Line 2,691 ⟶ 2,885:
reset()
{
}
enumerable() =>
}
Line 2,700 ⟶ 2,894:
{
var attempt := new Integer();
EvoAlgorithm.new(Target,C).forEach::(current)
{
console
Line 3,842 ⟶ 4,036:
end
</syntaxhighlight>
=={{Header|Insitux}}==
{{Trans|Clojure}}
Define the evolution parameters (values here per Wikipedia article), with a couple of problem constants.
<syntaxhighlight lang="insitux">
(var c 100) ;number of children in each generation
(var p 0.05) ;mutation probability
(var target "METHINKS IT IS LIKE A WEASEL")
(var tsize (len target))
(var alphabet (to-vec " ABCDEFGHIJLKLMNOPQRSTUVWXYZ"))
</syntaxhighlight>
Now the major functions. <code>fitness</code> simply counts the number of characters matching the target.
<syntaxhighlight lang="insitux">
(var fitness (comp @(map = target) (count val)))
(var perfect-fit? (comp fitness (= tsize)))
(var rand-char #(rand-pick alphabet))
(var mutate (map #(if (< (rand) p) (rand-char) %)))
</syntaxhighlight>
Finally evolve. At each generation, print the generation number, the parent, and the parent's fitness.
<syntaxhighlight lang="insitux">
(function evolve generation parent
(print (pad-left " " 3 generation) " " (... str parent) " " (fitness parent))
(return-when (perfect-fit? parent))
(let children (times c #(mutate parent))
fittest (max-by fitness (... vec parent children)))
(recur (inc generation) fittest))
(evolve 1 (times tsize rand-char))
</syntaxhighlight>
{{out}}
<pre>
1 LUUDSLXITIQ JREKRDIQFXBPJMBA 2
2 LUUDSLXITIQ LREKRDIQFXBPHMEA 3
...
10 LUFRSLKSTIQ CFHLIGANB WPHMEL 10
11 LUFRSLKSTIQ CF LIGANB WPHMEL 11
...
20 MUTRINKSAIT GF LITENB WPDSEL 18
21 METRINKSAIT NY LITENB WPDSEL 19
...
30 METWINKS IT N LITE B WEASEL 23
31 METWINKS IT N LITE B WEASEL 23
...
40 METHINKS IT IS LITE A WEASEL 27
41 METHINKS IT IS LITE A WEASEL 27
...
50 METHINKS IT IS LITE A WEASEL 27
51 METHINKS IT IS LIKE A WEASEL 28
</pre>
=={{header|J}}==
Line 4,220 ⟶ 4,480:
Generation: 50, Best: METHINKS IT IS LIKEZA WEASEL, fitness:1
Generation: 52, Best: METHINKS IT IS LIKE A WEASEL, fitness:0
</pre>
An attempt using ES6
by A.K.Bateman 2023
<syntaxhighlight lang="javascript">
"use strict"
const TARGET = "METHINKS IT IS LIKE A WEASEL";
const GENE_POOL = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ ';
const C = 100;
const MUTATION_RATE = 0.3;
function randomIdGenerator(length) {
return Math.floor(Math.random() * length);
}
function getGene() {
return GENE_POOL[randomIdGenerator(GENE_POOL.length)];
}
class Parent {
_arrayLength;
_genePool;
_geneGenerator;
constructor(arrayLength, genePool, geneGenerator) {
if (typeof arrayLength === 'number' && arrayLength > 0) {
this._arrayLength = arrayLength;
}
if (typeof genePool === 'string' && genePool.length > 0) {
this._genePool = [...genePool];
}
if (typeof geneGenerator === 'function') {
this._geneGenerator = geneGenerator;
}
}
generate() {
const letters = [];
while (letters.length < this._arrayLength) {
letters.push(this._geneGenerator());
}
return letters.join('');
}
}
function fitness(needle, target) {
if (needle.length !== target.length) return 0;
const needleArray = [...needle];
let count = 0;
[...target].forEach((item, index) => {
if (item === needleArray[index]) count++;
});
return count;
}
function mutate({ source, mutationRate }) {
if (typeof source !== 'string' || source.length === 0) return '';
const sourceLength = source.length;
const iterations = Math.floor(sourceLength * mutationRate);
const stringArray = [...source];
for(let i = 0; i < iterations; i++) {
const shouldReplace = Boolean(Math.floor(Math.random() * 2));
if(shouldReplace) {
const id = randomIdGenerator(sourceLength);
stringArray[id] = getGene();
}
}
return stringArray.join('');
}
function createMutants(parent, mutantNumber) {
const mutantArray = [];
for (let i = 0; i < mutantNumber; i++) {
const mutant = mutate({source: parent, mutationRate: MUTATION_RATE});
mutantArray.push(
{
mutant,
fitness: fitness(mutant, TARGET),
},
);
}
return mutantArray;
}
function helperInit(parentString, parentFitness) {
const mutant = createMutants(parentString, C)
.sort( (a,b) => a.fitness - b.fitness ).pop();
if (mutant.fitness >= parentFitness) {
return {
string: mutant.mutant,
fitness: mutant.fitness,
};
}
return {
string: parentString,
fitness: parentFitness,
};
}
function run() {
const parent = new Parent(TARGET.length, GENE_POOL, getGene);
let parentString = parent.generate();
let parentFitness = fitness(parentString, TARGET);
let genCount = 0;
while(parentString !== TARGET) {
const init = helperInit(parentString, parentFitness);
parentString = init.string;
parentFitness = init.fitness;
console.log(init.string);
genCount++;
}
console.log(`Ended in ${genCount} generations`);
}
run();
</syntaxhighlight>
example output:
<pre>
METHYNKS IT IS LIKE A WEASEL
METHYNKS IT IS LIKE A WEASEL
METHYNKS IT IS LIKE A WEASEL
METHYNKS IT IS LIKE A WEASEL
METHYNKS IT IS LIKE A WEASEL
METHINKS IT IS LIKE A WEASEL
Ended in 240 generations
</pre>
=={{header|jq}}==
{{Works with|jq}}
'''Works with gojq, the Go implementation of jq(*)'''
'''Works with jaq, the Rust implementation of jq(*)'''
In this entry, the "fitness" score is based on codepoint differences;
this has the effect of preserving correctly located spaces.
Notice also how the algorithm quickly achieves an approximate
solution but takes a while to arrive at the destination.
Since jq currently does not have a PRNG, the following assumes the availability
of /dev/random as a source of entropy. The output shown below was generated by
invoking jq in the pipeline:
<pre>
< /dev/random tr -cd '0-9' | fold -w 3 | $JQ -cnr -f evolutionary-algorithm.jq
</pre>
(*) For gojq and jaq, leading 0s must be stripped from the input, e.g. by
`sed -e '/^0./s/0//' -e '/^0./s/0//'`.
<syntaxhighlight lang="jq">
# Assumption: input consists of random three-digit numbers i.e. 000 to 999
def rand: input;
def set: "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
def abs:
if . < 0 then -. else . end;
def ichar:
if type == "number" then . else explode[0] end;
# Output: a pseudo-random character from set.
# $n should be a random number drawn from range(0; N) inclusive where N > set|length
# Input: an admissible character from `set` (ignored in this implementation)
def shift($n):
($n % (set|length)) as $i
| set[$i:$i+1];
# fitness: 0 indicates a perfect fit; greater numbers indicate worse fit.
def fitness($gold):
def diff($c; $d): ($c|ichar) - ($d|ichar) | abs;
. as $in
| reduce range(0;length) as $i (0; . + diff($in[$i:$i+1]; $gold[$i:$i+1]));
# Input: a string
# Output: a mutation of . such that each character is mutated with probability $r
def mutate($r):
# Output: a pseudo-random character from set
# $n should be a random number drawn from range(0; N) inclusive where N > set|length
def letter($n):
($n % (set|length)) as $i
| set[$i:$i+1];
. as $p
| reduce range(0;length) as $i ("";
rand as $rand
| if ($rand/1000) < $r then . + letter($rand)
else . + $p[$i:$i+1]
end );
# An array of $n children of the parent provided as input; $r is the mutation probability
def children($n; $r):
[range(0;$n) as $i | mutate($r)];
# Input: a "parent"
# Output: a single string
def next_generation($gold; $r):
([.] + children(100; $r))
| min_by( fitness($gold) );
# Evolve towards the target string provided as input, using $r as the mutation rate;
# `recurse` is used in order to show progress conveniently.
def evolve($r):
. as $gold
| (set|length) as $s
| (reduce range(0; $n) as $i (""; (rand % $s) as $j | . + set[$j:$j+1])) as $string
| {count: 0, $string }
| recurse (
if .string | fitness($gold) == 0 then empty
else .string |= next_generation($gold; $r)
| .count += 1
end);
"METHINKS IT IS LIKE A WEASEL" | evolve(0.05)
</syntaxhighlight>
{{output}}
<pre>
{"count":0,"string":"OIRSP AVNMTSSKOEIRBGDXZUBIQL"}
{"count":1,"string":"OIRSP AV MTSSKOEIRBGDXZUBIQL"}
{"count":2,"string":"OIRSP AV MTSAKOEIRBGD ZUBIQL"}
{"count":3,"string":"OIRSPCAV MTSAWOEIRBGD ZUBIQL"}
{"count":4,"string":"OIRJACAV MTEAWOEIRBGD ZUBIQL"}
{"count":5,"string":"OIRJACTV MTEAWOEIRBGD ZGBIQL"}
{"count":6,"string":"OIRJBCTV MTEAWAEIRBGD ZGBIJL"}
{"count":7,"string":"OIRJBCTV MTEAWAEIRBGD ZGBTJL"}
{"count":8,"string":"UIRJBCTV MT AWFEIRBGG ZGBTJL"}
{"count":9,"string":"UIRJBMTV MT AWFEIRBGG ZGBTJL"}
{"count":10,"string":"JIRJEMTV MT AWFEIKGGG ZGBTJL"}
{"count":11,"string":"JIRJEMKV MT AWFEIKGGG XGBTJL"}
{"count":12,"string":"JIRJEMKV MT AWFEIKGGG XGBTAL"}
{"count":13,"string":"JIRJEMKV MT KWFEIKGGG XGBTAL"}
{"count":14,"string":"JFRJEMKP MT KWFEIKGGG XGBTAL"}
{"count":15,"string":"JFRJEMKP MT KWFJIKGGG XGBTAL"}
{"count":16,"string":"JFRJEMKT MT KQFJIKGGG XGBTAL"}
{"count":17,"string":"JFRJEMKT MT HQFJIKGGG XGBTAL"}
{"count":18,"string":"JFRJEMKT MT HQFJIKGGC XGBTAL"}
{"count":19,"string":"LFRJEMKT MT HQFJIIGGC XGATFL"}
{"count":20,"string":"LFRJIMKT MT HQFJIIGGC XGATFL"}
...
{"count":61,"string":"MFTHINKS JT IR LIKE A WEAREL"}
{"count":62,"string":"MFTHINKS JT IR LIKE A WEAREL"}
{"count":63,"string":"MFTHINKS JT IR LIKE A WEAREL"}
{"count":64,"string":"MFTHINKS JT IR LIKE A WEAREL"}
{"count":65,"string":"MFTHINKS JT IR LIKE A WEAREL"}
{"count":66,"string":"MFTHINKS JT IR LIKE A WEAREL"}
{"count":67,"string":"MFTHINKS JT IR LIKE A WEAREL"}
{"count":68,"string":"MFTHINKS JT IR LIKE A WEAREL"}
{"count":69,"string":"MFTHINKS IT IR LIKE A WEAREL"}
{"count":70,"string":"MFTHINKS IT IR LIKE A WEAREL"}
{"count":71,"string":"MFTHINKS IT IS LIKE A WEAREL"}
{"count":72,"string":"MFTHINKS IT IS LIKE A WEAREL"}
{"count":73,"string":"MFTHINKS IT IS LIKE A WEAREL"}
{"count":74,"string":"MFTHINKS IT IS LIKE A WEAREL"}
{"count":75,"string":"MFTHINKS IT IS LIKE A WEAREL"}
{"count":76,"string":"METHINKS IT IS LIKE A WEAREL"}
{"count":77,"string":"METHINKS IT IS LIKE A WEAREL"}
{"count":78,"string":"METHINKS IT IS LIKE A WEAREL"}
{"count":79,"string":"METHINKS IT IS LIKE A WEAREL"}
{"count":80,"string":"METHINKS IT IS LIKE A WEAREL"}
{"count":81,"string":"METHINKS IT IS LIKE A WEAREL"}
{"count":82,"string":"METHINKS IT IS LIKE A WEASEL"}
</pre>
Line 6,938 ⟶ 7,475:
@alphabet.roll(target.chars).join,
{ max :by(&fitness), mutate($_, .001) xx C } ... target;
print "\n";
</syntaxhighlight>
Line 7,712 ⟶ 8,250:
until best = 0;
end func;</syntaxhighlight>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program weasel;
setrandom(0);
target := "METHINKS IT IS LIKE A WEASEL";
charset := {c : c in " ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
mutation_rate := 0.1;
generation_size := 100;
loop init
current := +/[random charset : c in target];
doing
print(lpad(str fitness(current, target), 3), current);
while current /= target do
current := next_generation(
current, target, mutation_rate, generation_size, charset);
end loop;
proc fitness(candidate, target);
return #[i : i in [1..#target] | candidate(i) /= target(i)];
end proc;
proc mutate(candidate, mutation_rate, charset);
return +/[
if random 1.0 < mutation_rate
then random charset
else c
end
: c in candidate
];
end proc;
proc next_generation(
parent, target, mutation_rate, generation_size, charset);
children := {
[fitness(c:=mutate(parent, mutation_rate, charset), target), c]
: i in [1..generation_size]
};
return random children{min/domain children};
end proc;
end program;</syntaxhighlight>
{{out}}
<pre> 25 DSBHHVDSLFJFYAXRTZEAXBRDPATW
24 DSBHHMDSLFJ YAXRTZEAXBRDPATW
23 DSBHHMDSLFT YAXRTZEAXBRDJATW
20 DSBHHMDSLFT YJXRTZEAX WDJSTW
...
1 METHINKS IT IS LPKE A WEASEL
1 METHINKS IT IS LQKE A WEASEL
0 METHINKS IT IS LIKE A WEASEL</pre>
=={{header|SequenceL}}==
Line 8,905 ⟶ 9,494:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var target = "METHINKS IT IS LIKE A WEASEL"
| |||