Evolutionary algorithm: Difference between revisions
Added Easylang
(Added Easylang) |
|||
(31 intermediate revisions by 17 users not shown) | |||
Line 45:
{{trans|Python}}
<
V alphabet = ‘ ABCDEFGHIJLKLMNOPQRSTUVWXYZ’
V p = 0.05
Line 63:
parent = min(copies, key' x -> neg_fitness(x))
print((‘#3’.format(i))‘ ’parent.join(‘’))
i++</
{{out}}
Line 85:
=={{header|8080 Assembly}}==
<
COPIES: equ 100 ; Amount of copies to make
fname1: equ 5Dh ; First filename on command line (used for RNG seed)
Line 246:
maxptr: ds 2 ; Pointer to copy with best fitness
parent: equ $ ; Store current parent here
kids: equ $+tgtsz ; Store mutated copies here</
{{out}}
Line 275:
=={{header|8086 Assembly}}==
<
cpu 8086
MRATE: equ 26 ; Mutation rate (MRATE/256)
Line 397:
rnddat: resb 4 ; RNG state
parent: resb target.size ; Place to store current parent
kids: resb COPIES*target.size ; Place to store children</
{{out}}
Line 426:
=={{header|8th}}==
<
\ RosettaCode challenge http://rosettacode.org/wiki/Evolutionary_algorithm
\ Responding to the criticism that the implementation was too directed, this
Line 520:
"METHINKS IT IS LIKE A WEASEL"
setup-random initial-string evolve bye</
The output:
Line 537:
Very simple fitness determination. For testing purposes you can add a static seed value to the RNG initializations (sample output uses '12345' for both).
<
with Ada.Numerics.Discrete_Random;
with Ada.Numerics.Float_Random;
Line 660:
-- evolve!
Evolve;
end Evolution;</
sample output:
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}}==
{{trans|C}}
<
fitness(data t, data b)
{
Line 755 ⟶ 815:
return 0;
}</
{{out}}
<pre>23 EAAXIZJROVOHSKREBNSAFHEKF B
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 874 ⟶ 948:
Finding the target string on an Amstrad CPC takes a bit less than 45 minutes.
<
20 cc=100
30 prop=0.05
Line 908 ⟶ 982:
330 if sc=sl then print "We have a weasel!":? "Time: "(time-start)/300:end
340 cp=bsi
350 goto 150</
Output during calculation (excerpt):
Line 924 ⟶ 998:
{{works with|Dyalog APL}}
<
⍺←0.1
target←'METHINKS IT IS LIKE A WEASEL'
Line 941 ⟶ 1,015:
}charset[?(⍴target)/⍴charset]
}
</syntaxhighlight>
{{out}}
Line 968 ⟶ 1,042:
METHINKS IT IS LIKE A WEASEL
METHINKS IT IS LIKE A WEASEL</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">target: "METHINKS IT IS LIKE A WEASEL"
alphabet: [` `] ++ @`A`..`Z`
p: 0.05
c: 100
negFitness: function [trial][
result: 0
loop 0..dec size trial 'i ->
if target\[i] <> trial\[i] -> inc 'result
return result
]
mutate: function [parent][
result: ""
loop parent 'c ->
'result ++ (p > random 0.0 1.0)? -> sample alphabet -> c
return result
]
parent: ""
do.times: size target ->
'parent ++ sample alphabet
j: 0
copies: []
while [parent <> target][
'copies ++ map c 'i -> mutate parent
best: first copies
loop 1..dec size copies 'i [
if (negFitness copies\[i]) < negFitness best ->
best: copies\[i]
]
parent: best
print [pad to :string j 2 parent]
inc 'j
]</syntaxhighlight>
{{out}}
<pre> 0 JBTBAFNWA YYZTOUBPIUUSPTFKYK
1 JBTBAFNWA YYFTOUBPIUU PTFKYK
2 MBTBAFNWA YYFTOUBPDUU PTFKYK
3 MBTBCMNWA YYFTOUBPDUU PTFKEK
4 MBTBCMNWA YDFSOUBPDUU PTFKEK
...
27 METHINVSV TDIS LIKE A WZASEK
28 METHINVSV TDIS LIKE A WZASEL
29 METHINVSV TDIS LIKE A WZASEL
30 METHINVSV TDIS LIKE A WZASEL
31 METHINVSV TDIS LIKE A WZASEL
32 METHINVSV TDIS LIKE A WZASEL
33 METHINVSV TDIS LIKE A WZASEL
34 METHINVSV TDIS LIKE A WZASEL
35 METHINVS TMIS LIKE A WZASEL
...
57 METHINVS ITMIS LIKE A WEASEL
58 METHINVS IT IS LIKE A WEASEL
59 METHINVS IT IS LIKE A WEASEL
60 METHINKS IT IS LIKE A WEASEL</pre>
=={{header|AutoHotkey}}==
<
target := "METHINKS IT IS LIKE A WEASEL"
targetLen := StrLen(target)
Line 1,026 ⟶ 1,166:
totalFit++
Return totalFit
}</
Output:
<pre>10: DETRNNKR IAQPFLNVKZ AMXEASEL, fitness: 14
Line 1,040 ⟶ 1,180:
=={{header|AWK}}==
I apply the rate to each character in each generated child. The number of generations required seems to be really sensitive to the rate. I used the default seeding in GNU awk to obtain the results below. I suspect the algorithm used to generate the pseudo-random numbers may also influence the rapidity of convergence but I haven't investigated that yet. The output shown was obtained using GNU Awk 3.1.5. BusyBox v1.20.0.git also works but using the same rate generates 88 generations before converging.
<
#!/bin/awk -f
function randchar(){
Line 1,104 ⟶ 1,244:
}
</syntaxhighlight>
Output:
<pre>
Line 1,120 ⟶ 1,260:
#
</pre>
=={{header|BASIC}}==
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> target$ = "METHINKS IT IS LIKE A WEASEL"
parent$ = "IU RFSGJABGOLYWF XSMFXNIABKT"
mutation_rate = 0.5
children% = 10
DIM child$(children%)
REPEAT
bestfitness = 0
bestindex% = 0
FOR index% = 1 TO children%
child$(index%) = FNmutate(parent$, mutation_rate)
fitness = FNfitness(target$, child$(index%))
IF fitness > bestfitness THEN
bestfitness = fitness
bestindex% = index%
ENDIF
NEXT index%
parent$ = child$(bestindex%)
PRINT parent$
UNTIL parent$ = target$
END
DEF FNfitness(text$, ref$)
LOCAL I%, F%
FOR I% = 1 TO LEN(text$)
IF MID$(text$, I%, 1) = MID$(ref$, I%, 1) THEN F% += 1
NEXT
= F% / LEN(text$)
DEF FNmutate(text$, rate)
LOCAL C%
IF rate > RND(1) THEN
C% = 63+RND(27)
IF C% = 64 C% = 32
MID$(text$, RND(LEN(text$)), 1) = CHR$(C%)
ENDIF
= text$</syntaxhighlight>
=={{header|Batch File}}==
<
@echo off
setlocal enabledelayedexpansion
Line 1,211 ⟶ 1,393:
for /l %%i in (1,1,28) do set %returnarray%=!%returnarray%! !%returnarray%%%i!
exit /b
</syntaxhighlight>
{{out}}
Sample Output:
Line 1,245 ⟶ 1,427:
Done.
</pre>
=={{header|C}}==
<
#include <stdlib.h>
#include <string.h>
Line 1,354 ⟶ 1,495:
return 0;
}</
iter 1, score 25: WKVVTFJUHOMQJN YRTEQAGDVSKXC
iter 2, score 25: WKVVTFJUHOMQJN YRTEQAGDVSKXC
Line 1,361 ⟶ 1,502:
iter 221, score 1: METHINKSHIT IS LIKE A WEASEL
iter 222, score 1: METHINKSHIT IS LIKE A WEASEL
iter 223, score 0: METHINKS IT IS LIKE A WEASEL</
=={{header|C sharp|C#}}==
Line 1,367 ⟶ 1,508:
{{works with|C sharp|C#|3+}}
<
using System.Collections.Generic;
using System.Linq;
Line 1,420 ⟶ 1,561:
Console.WriteLine("END: #{0,6} {1,20}", i, parent);
}
}</
Example output:
Line 1,491 ⟶ 1,632:
=={{header|C++}}==
<
#include <cstdlib>
#include <iostream>
Line 1,600 ⟶ 1,741:
}
std::cout << "final string: " << parent << "\n";
}</
Example output:
<pre>
Line 1,651 ⟶ 1,792:
=={{header|Ceylon}}==
<
DefaultRandom
Line 1,699 ⟶ 1,840:
print("mutated into target in ``generationCount`` generations!");
}</
=={{header|Clojure}}==
Define the evolution parameters (values here per Wikipedia article), with a couple of problem constants.
<
(def p 0.05) ;mutation probability
Line 1,709 ⟶ 1,850:
(def tsize (count target))
(def alphabet " ABCDEFGHIJLKLMNOPQRSTUVWXYZ")</
Now the major functions. ''fitness'' simply counts the number of characters matching the target.
<
(defn perfectly-fit? [s] (= (fitness s) tsize))
(defn randc [] (rand-nth alphabet))
(defn mutate [s] (map #(if (< (rand) p) (randc) %) s))</
Finally evolve. At each generation, print the generation number, the parent, and the parent's fitness.
<
(println generation, (apply str parent), (fitness parent))
(if-not (perfectly-fit? parent)
(let [children (repeatedly c #(mutate parent))
fittest (apply max-key fitness parent children)]
(recur (inc generation), fittest))))</
=={{header|CLU}}==
<
f: int := 0
for i: int in int$from_to(1,string$size(s)) do
Line 1,775 ⟶ 1,916:
stream$putl(po, m)
end
end start_up</
{{out}}
<pre>CQWBQKNNFKEOLFLXHGJYEWZYULBQ
Line 1,813 ⟶ 1,954:
=={{header|COBOL}}==
For testing purposes, you can comment out the first two sentences in the <tt>CONTROL-PARAGRAPH</tt> and the program will then use the same sequence of pseudo-random numbers on each run.
<
program-id. evolutionary-program.
data division.
Line 1,900 ⟶ 2,041:
fittest-paragraph.
move fitness to highest-fitness.
move child to fittest.</
{{out}}
<div style="height:50ex;overflow:scroll">
Line 2,100 ⟶ 2,241:
=={{header|ColdFusion}}==
<
<Cfset theString = 'METHINKS IT IS LIKE A WEASEL'>
<cfparam name="parent" default="">
Line 2,168 ⟶ 2,309:
</Cfloop>
</syntaxhighlight>
<pre>
#1 7% fit: VOPJOBSYPTTUNYYSAFHTPJUIAIL
Line 2,196 ⟶ 2,337:
Finding the target string takes roughly two hours on a Commodore 64.
<
20 Z$="METHINKS IT IS LIKE A WEASEL"
30 L=LEN(Z$)
Line 2,226 ⟶ 2,367:
300 FORI=1TOL:IFX(K,I)THENPRINTCHR$(64+X(K,I));:GOTO320
310 PRINT" ";
320 NEXT:PRINT"<":RETURN</
Output during calculation (excerpt):
Line 2,257 ⟶ 2,398:
=={{header|Common Lisp}}==
<
"Closeness of string to target; lower number is better"
(loop for c1 across string
Line 2,295 ⟶ 2,436:
(n 0 (1+ n)))
((string= target parent) (format t "Generation ~A: ~S~%" n parent))
(format t "Generation ~A: ~S~%" n parent))))</
Sample output:
<pre>CL-USER> (evolve-gens "METHINKS IT IS LIKE A WEASEL" 100 0.05)
Line 2,345 ⟶ 2,486:
Mutates one character at a time, with only on offspring each generation (which competes against the parent):
<
(loop for a across s1
for b across s2 count(char/= a b)))
Line 2,367 ⟶ 2,508:
(format t "~5d: ~a (~d)~%" gen str fit))))
(evolve 1 " ABCDEFGHIJKLMNOPQRSTUVWXYZ" "METHINKS IT IS LIKE A WEASEL")</
57: DYZTOREXDIL ZCEUCSHRVHBEPGJE (25)
83: DYZTOREX IL ZCEUCSHRVHBEPGJE (24)
Line 2,393 ⟶ 2,534:
1220: METHINKS IT IS LIKE AHBEASEL (2)
1358: METHINKS IT IS LIKE AHWEASEL (1)
2610: METHINKS IT IS LIKE A WEASEL (0)</
=={{header|D}}==
<
enum target = "METHINKS IT IS LIKE A WEASEL"d;
Line 2,413 ⟶ 2,554:
writefln("Gen %2d, dist=%2d: %s", gen, parent.fitness, parent);
}
}</
{{out}}
<pre>Generation 0, dist=25: PTJNKPFVJFTDRSDVNUB ESJGU MF
Line 2,440 ⟶ 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].
=={{header|E}}==
<
pragma.enable("accumulator")
Line 2,487 ⟶ 2,707:
}
weasel()</
=={{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}}==
<
(require 'sequences)
(define ALPHABET (list->vector ["A" .. "Z"] ))
Line 2,529 ⟶ 2,790:
(set! parent (select parent target rate copies))
))
</syntaxhighlight>
{{out}}
<pre>
Line 2,565 ⟶ 2,826:
=={{header|Elena}}==
ELENA
<
import extensions;
import extensions'text;
Line 2,584 ⟶ 2,845:
{
randomString()
= 0.repeatTill(self).selectBy::(x => randomChar).summarize(new StringWriter());
fitnessOf(s)
Line 2,590 ⟶ 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,624 ⟶ 2,885:
reset()
{
}
enumerable() =>
}
Line 2,633 ⟶ 2,894:
{
var attempt := new Integer();
EvoAlgorithm.new(Target,C).forEach::(current)
{
console
Line 2,641 ⟶ 2,902:
console.readChar()
}</
{{out}}
<pre>
Line 2,696 ⟶ 2,957:
Print current gen and most fit offspring if more fit than parent.<br>
Print the target and the total number of generations (iterations) it took to reach it.<br>
<
def show(offspring,i) do
IO.puts "Generation: #{i}, Offspring: #{offspring}"
Line 2,759 ⟶ 3,020:
end
Evolution.select("METHINKS IT IS LIKE A WEASEL")</
{{out}}
Line 2,817 ⟶ 3,078:
=={{header|Erlang}}==
<
-export([run/0]).
Line 2,878 ⟶ 3,139:
random_string(N-1,[random_character()|Acc]).
</syntaxhighlight>
=={{header|Euphoria}}==
<
function random_generation(integer len)
sequence s
Line 2,931 ⟶ 3,192:
iter += 1
end while
printf(1,"Finally, \"%s\"\n",{parent})</
Output:
Line 2,959 ⟶ 3,220:
=={{header|F Sharp|F#}}==
<
//A functional implementation of Evolutionary algorithm
//Nigel Galloway February 7th., 2018
Line 2,970 ⟶ 3,231:
evolution n []
let n = evolution (Array.init 28 (fun _->alphabet.[G.Next()%27]))
</syntaxhighlight>
Real: 00:00:00.021, CPU: 00:00:00.050, GC gen0: 1, gen1: 0
<br>
Line 3,016 ⟶ 3,277:
=={{header|Factor}}==
<
random sequences strings ;
FROM: math.extras => ... ;
Line 3,052 ⟶ 3,313:
"Finished in %d generations." printf ;
MAIN: main</
{{out}}
<pre>
Line 3,067 ⟶ 3,328:
=={{header|Fantom}}==
<
class Main
{
Line 3,124 ⟶ 3,385:
}
}
</syntaxhighlight>
=={{header|Forth}}==
{{works with|4tH|3.60.0}}
<
\ target string
s" METHINKS IT IS LIKE A WEASEL" sconstant target
Line 3,200 ⟶ 3,461:
;
weasel</
Output:
<pre>
Line 3,221 ⟶ 3,482:
{{works with|Fortran|2003}}
<
!***************************************************************************************************
module evolve_routines
Line 3,357 ⟶ 3,618:
end program evolve
!***************************************************************************************************
</syntaxhighlight>
The output is:
<syntaxhighlight lang="text">
iter best fitness
0 PACQXJB CQPWEYKSVDCIOUPKUOJY 459
Line 3,379 ⟶ 3,640:
70 MESHINKS IT IS LIKE A WEASEL 1
75 METHINKS IT IS LIKE A WEASEL 0
</syntaxhighlight>
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 3,465 ⟶ 3,726:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>iteration best fit Parent
Line 3,499 ⟶ 3,760:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Weasel_program}}
'''Solution'''
[[File:Fōrmulæ - Evolutionary algorithm 01.png]]
'''Test case'''
[[File:Fōrmulæ - Evolutionary algorithm 02.png]]
[[File:Fōrmulæ - Evolutionary algorithm 03.png]]
'''A graph of the fitness function'''
[[File:Fōrmulæ - Evolutionary algorithm 04.png]]
[[File:Fōrmulæ - Evolutionary algorithm 05.png]]
=={{header|Go}}==
I took the liberty to use <code>[]byte</code> for the "strings" mentioned in the task description. Go has a native string type, but in this case it was both easier and more efficient to work with byte slices and just convert to string when there was something to print.
<
import (
Line 3,571 ⟶ 3,844:
}
}
}</
{{out}}
<div style='height: 15em; overflow: scroll'><pre>
Line 3,603 ⟶ 3,876:
{{works with|GHC|7.6.3}}
<
import Control.Monad
import Data.List
Line 3,650 ⟶ 3,923:
genes <- replicateM r $ randomRIO (bounds charSet)
let parent = map (charSet!) genes
evolve parent 1 mutateRate</
Example run in GHCi:
<pre>*Main> main
Line 3,662 ⟶ 3,935:
I find this easier to read.
<
import Data.List
import Data.Ord
Line 3,696 ⟶ 3,969:
where fmtd = parent ++ ": " ++ show (fitness parent) ++ " (" ++ show n ++ ")"
main = origin >>= converge 0</
Example:
<pre>YUZVNNZ SXPSNGZFRHZKVDOEPIGS: 2 (0)
Line 3,711 ⟶ 3,984:
=={{header|Icon}} and {{header|Unicon}}==
<
procedure fitness(s)
Line 3,762 ⟶ 4,035:
write("At generation " || gen || " we found a string with perfect fitness at " || current_fitness || " reading: " || parent)
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 3,768 ⟶ 4,107:
'''Solution:'''<br>
Using sum of differences from the target for fitness, i.e. <code>0</code> is optimal fitness.
<
NPROG=: 100 NB. number of progeny (C)
MRATE=: 0.05 NB. mutation rate
Line 3,781 ⟶ 4,120:
while =: conjunction def '(] , (u {:))^:(v {:)^:_ ,:'
evolve=: nextgen while (0 < fitness) create</
'''Example usage:'''<br>
Returns list of best solutions at each generation until converged.
<
filter evolve 'METHINKS IT IS LIKE A WEASEL'
XXURVQXKQXDLCGFVICCUA NUQPND
MEFHINVQQXT IW LIKEUA WEAPEL
METHINVS IT IW LIKEUA WEAPEL
METHINKS IT IS LIKE A WEASEL</
'''Alternative solution:'''<br>
Using explicit versions of <code>mutate</code> and <code>evolve</code> above.
<
NPROG=: 100 NB. "C" from specification
Line 3,820 ⟶ 4,159:
log iter;val;parent
parent
)</
'''Example Usage:'''
<
#0 fitness: 27 ; YGFDJFTBEDB FAIJJGMFKDPYELOA
#50 fitness: 2 ; MEVHINKS IT IS LIKE ADWEASEL
#76 fitness: 0 ; METHINKS IT IS LIKE A WEASEL
METHINKS IT IS LIKE A WEASEL</
=={{header|Java}}==
Line 3,833 ⟶ 4,172:
'''(Close)''' {{trans|Python}}
<
import java.util.Random;
Line 3,891 ⟶ 4,230:
}
}</
Output:
<pre>100: MEVHIBXSCG TP QIK FZGJ SEL, fitness: 13, rate: 0.4875
Line 3,902 ⟶ 4,241:
Using cross-browser techniques to support Array.reduce and Array.map
<
/* Compatibility code to reduce an array
Line 4,131 ⟶ 4,470:
document.write("Generation: " + generation + ", Best: " + fittest.individual.join("") + ", fitness:" + fittest.score + "<br>");
}
result = evolver.run(showProgress);</
Output:
<pre>
Line 4,141 ⟶ 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 4,146 ⟶ 4,762:
{{works with|Julia|0.6}}
<
function mutate(str::AbstractString, rate::Float64)
L = collect(Char, " ABCDEFGHIJKLMNOPQRSTUVWXYZ")
Line 4,169 ⟶ 4,785:
end
evolve("IU RFSGJABGOLYWF XSMFXNIABKT", "METHINKS IT IS LIKE A WEASEL", 0.08998, 100)</
{{out}}
Line 4,184 ⟶ 4,800:
=={{header|Kotlin}}==
<
val target = "METHINKS IT IS LIKE A WEASEL"
Line 4,217 ⟶ 4,833:
}
println("Evolution found target after $i generations")
}</
=={{header|Liberty BASIC}}==
<
'mutaterate has to be greater than 1 or it will not mutate
mutaterate = 2
Line 4,288 ⟶ 4,904:
End If
Next i
End Function</
=={{header|Logo}}==
<
to distance :w
Line 4,334 ⟶ 4,950:
make "trials :trials + 1
]
end</
=={{header|Lua}}==
{{works with|Lua|5.1+}}
<
local alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
local c, p = 100, 0.06
Line 4,390 ⟶ 5,006:
parent, step = bestChild, step + 1
printStep(step, parent, bestFitness)
end</
=={{header|M2000 Interpreter}}==
===Version 1===
<syntaxhighlight lang="m2000 interpreter">
Module WeaselAlgorithm {
Print "Evolutionary Algorithm"
Line 4,453 ⟶ 5,069:
WeaselAlgorithm
</syntaxhighlight>
{{out}}
Line 4,495 ⟶ 5,111:
Also here we have one Mutate function which change letters using 5% probability for each place in the parent string.
<syntaxhighlight lang="m2000 interpreter">
Module WeaselAlgorithm2 {
Print "Evolutionary Algorithm"
Line 4,549 ⟶ 5,165:
}
WeaselAlgorithm2
</syntaxhighlight>
=={{header|m4}}==
Line 4,561 ⟶ 5,177:
This is not the best use of m4, and I am far from an m4 guru, but it seemed unlikely anyone else was going to write an m4 example for this task. The better my m4 skills, the better I am going to be at ''everything'' that can be preprocessed, and at GNU Autotools (which, unlike many, I like a lot). So I wrote this.
<
# Get a random number from 0 to one less than $1.
Line 4,652 ⟶ 5,268:
divert`'dnl
[parent]
repeat_until_equal(parent,10,10)</
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
alphabet = Append[CharacterRange["A", "Z"], " "];
fitness = HammingDistance[target, #] &;
Line 4,671 ⟶ 5,287:
mutate[target, 1],
fitness@# > 0 &
] // ListAnimate</
=={{header|MATLAB}}==
Line 4,678 ⟶ 5,294:
To use this code, create a folder in your MATLAB directory titled "@EvolutionaryAlgorithm". Within that folder save this code in a file named "EvolutionaryAlgorithm.m".
<
classdef EvolutionaryAlgorithm
Line 4,897 ⟶ 5,513:
end %methods
end %classdef</
Sample Output: (Some evolutionary cycles omitted for brevity)
<
Target: METHINKS IT IS LIKE A WEASEL
Parent: UVEOCXXFBGDCSFNMJQNWTPJ PCVA
Line 4,925 ⟶ 5,541:
100: METHIXKS YT IS LIKE A WEASEL - Fitness: 26
150: METHINKS YT IS LIKE A WEASEL - Fitness: 27
195: METHINKS IT IS LIKE A WEASEL - Fitness: 28</
Line 4,932 ⟶ 5,548:
Presented is very efficient and vectorized version of the genetic algorithm. To run the algorithm simply copy and paste the code into a script and hit run. You can adjust the style of selection and crossover used to learn more about how they effect solutions. The algorithm can also handle any target string that uses ASCII characters and will allow for any phrase to be used regardless of length.
<syntaxhighlight lang="matlab">
%% Genetic Algorithm -- Solves For A User Input String
Line 5,043 ⟶ 5,659:
toc % Ends timer and prints elapsed time
</syntaxhighlight>
Sample Output: (The Algorithm was run with 1000 population members, Tournament Selection (with tournament size of 4), 1-Point Crossover, and a mutation rate of 10%).
<syntaxhighlight lang="matlab">
Gen: 1 | Fitness: 465 | C�I1%G+<%?R�8>9�JU#(E�UO�PHI
Gen: 2 | Fitness: 429 | W=P6>D�I)VU6$T 99,� B�BMP0JH
Line 5,089 ⟶ 5,705:
Gen: 46 | Fitness: 0 | METHINKS IT IS LIKE A WEASEL
Elapsed time is 0.099618 seconds.
</syntaxhighlight>
=={{header|Nanoquery}}==
<
target = "METHINKS IT IS LIKE A WEASEL"
Line 5,175 ⟶ 5,791:
iter += 1
end</
{{out}}
Line 5,198 ⟶ 5,814:
=={{header|Nim}}==
{{trans|Python}}
<
const
Line 5,234 ⟶ 5,850:
echo i, " ", parent
inc i</
{{out}}
Line 5,249 ⟶ 5,865:
=={{header|Objeck}}==
{{trans|Java}}
<
class Evolutionary {
target : static : String;
Line 5,339 ⟶ 5,955:
}
}
}</
Output:
Line 5,362 ⟶ 5,978:
=={{header|OCaml}}==
<
let charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
let tlen = String.length target
Line 5,402 ⟶ 6,018:
incr i
done;
Printf.printf "%5d - '%s'\n" !i parent</
=={{header|Octave}}==
{{trans|R}}
<
target = split("METHINKS IT IS LIKE A WEASEL", "");
charset = ["A":"Z", " "];
Line 5,459 ⟶ 6,075:
endwhile
disp(parent');
</syntaxhighlight>
=={{header|Oforth}}==
<
5 Constant new: RATE
Line 5,482 ⟶ 6,098:
ListBuffer init(C, #[ parent mutate ]) dup add(parent)
maxFor(#[ target fitness ]) dup ->parent . dup println 1+
] drop ;</
{{out}}
Line 5,528 ⟶ 6,144:
=={{header|OoRexx}}==
Run with Open Object Rexx 4.1.0 by IBM Corporation 1995,2004 Rexx LA 2005-2010. Host OS: Microsoft Windows 7.
<
/* Weasel.rex - Me thinks thou art a weasel. - G,M.D. - 2/25/2011 */
arg C M
Line 5,583 ⟶ 6,199:
end
return result
</syntaxhighlight>
Output:
<div style='height: 15em; overflow: scroll'><pre>
Line 5,621 ⟶ 6,237:
=={{header|OxygenBasic}}==
The algorithm pared down to the essentials. It takes around 1200 to 6000 mutations to attain the target. Fitness is measured by the number of beneficial mutations. The cycle ends when this is equal to the string length.
<
'EVOLUTION
Line 5,662 ⟶ 6,278:
end do
print progeny " " gens 'RESULT (range 1200-6000 generations)
</syntaxhighlight>
=={{header|Oz}}==
<
Target = "METHINKS IT IS LIKE A WEASEL"
C = 100
Line 5,724 ⟶ 6,340:
end
in
{Main}</
=={{header|PARI/GP}}==
Line 5,730 ⟶ 6,346:
This code is inefficient (tens of milliseconds) since it converts back and forth between string and vector format. A more efficient version would keep the information in a Vecsmall instead.
<
fitness(s)=-dist(Vec(s),Vec(target));
dist(u,v)=sum(i=1,min(#u,#v),u[i]!=v[i])+abs(#u-#v);
Line 5,775 ⟶ 6,391:
ct;
}
evolve(35,.05)</
=={{header|Pascal}}==
Line 5,781 ⟶ 6,397:
This Pascal version of the program displays the initial random string and every hundredth generation after that. It also displays the final generation count. Mutation happens relatively slowly, about once in every 1000 characters, but this can be changed by altering the RATE constant. Lower values for RATE actually speed up the mutations.
<
CONST
Line 5,888 ⟶ 6,504:
WRITE('The string was matched in ');
WRITELN(GENERATIONS, ' generations.')
END.</
=={{header|Perl}}==
Line 5,894 ⟶ 6,510:
This implementation usually converges in less than 70 iterations.
<
use List::MoreUtils 'false';
Line 5,938 ⟶ 6,554:
map {mutate $mutation_rate, $parent}
1 .. $C;
print @$parent, "\n";}</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">target</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"METHINKS IT IS LIKE A WEASEL"</span><span style="color: #0000FF;">,</span>
Line 5,979 ⟶ 6,595:
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Finally, \"%s\"\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">parent</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 6,002 ⟶ 6,618:
=={{header|PHP}}==
<
define('TARGET','METHINKS IT IS LIKE A WEASEL');
define('TBL','ABCDEFGHIJKLMNOPQRSTUVWXYZ ');
Line 6,049 ⟶ 6,665:
} while($best);
</syntaxhighlight>
Sample Output:
<pre>
Line 6,061 ⟶ 6,677:
=={{header|Picat}}==
<
_ = random2(),
Target = "METHINKS IT IS LIKE A WEASEL",
Line 6,144 ⟶ 6,760:
NextFitness := XF
end
end.</
=={{header|PicoLisp}}==
This example uses 'gen', the genetic function in "lib/simul.l"
<
(setq *Target (chop "METHINKS IT IS LIKE A WEASEL"))
Line 6,185 ⟶ 6,801:
C ) ) # return the current char
A ) )
fitness ) # Selection function</
Output:
<pre>RQ ASLWWWI ANSHPNABBAJ ZLTKX
Line 6,200 ⟶ 6,816:
the rate is fixed at 2 as that is the lowest most successful rate still in the spirit of the original proposal (where mutation allows a previously successful change to be undone). if the rate is 1 than every successful character change can not change again (because it would not cause an improvement and thus be rejected.)
<
string mutate(string data, int rate)
Line 6,243 ⟶ 6,859:
}
}
}</
Output:
Line 6,278 ⟶ 6,894:
=={{header|Pony}}==
{{trans|Java}}
<
actor Main
Line 6,350 ⟶ 6,966:
end
end
consume ret_val</
Output:
<pre>100: UMMMDNKR IEIIB IIKZ A THAHEL, fitness: 14, rate: 0.455
Line 6,361 ⟶ 6,977:
'''Alternative solution:'''<br>
Using a more OO approach that leverages classes for encapsulation.
<
use "collections"
Line 6,475 ⟶ 7,091:
until best.string == desired.string end
env.out.print(best.string + ", " + iterations.string())</
Output:
Line 6,486 ⟶ 7,102:
=={{header|Prolog}}==
{{works with|SWI Prolog|6.2.6 by Jan Wielemaker, University of Amsterdam}}
<
rndAlpha(64, 32). % Generate a single random character
Line 6,517 ⟶ 7,133:
weasel :- % Chance->probability for a mutation, T=Target, Start=initial text
target(T), length(T, Len), rndTxt(Len, Start), Chance is 1 - (1/(Len+1)),
!, weasel(0, Chance, T, Start).</
Output:
<pre> time(weasel).
Line 6,538 ⟶ 7,154:
=={{header|PureBasic}}==
<
Define.s target$ = "METHINKS IT IS LIKE A WEASEL"
Define.s charSet$ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
Line 6,608 ⟶ 7,224:
Wend
PrintN("Press any key to exit"): Repeat: Until Inkey() <> ""</
=={{header|Python}}==
Using lists instead of strings for easier manipulation, and a mutation rate that gives more mutations the further the parent is away from the target.
<
from random import choice, random
Line 6,658 ⟶ 7,274:
parent2 = max(copies[center:], key=fitness)
parent = max(mate(parent1, parent2), key=fitness)
que()</
Sample output
Line 6,668 ⟶ 7,284:
A simpler Python version that converges in less steps:
<
target = list("METHINKS IT IS LIKE A WEASEL")
Line 6,688 ⟶ 7,304:
parent = min(copies, key=neg_fitness)
print "%3d" % i, "".join(parent)
i += 1</
=={{header|R}}==
<
## Easier if the string is a character vector
Line 6,743 ⟶ 7,359:
}
}
.printGen(parent, target, i)</
output:
Line 6,759 ⟶ 7,375:
Very close to former solution, but a bit easier.
<
set.seed(42)
target= unlist(strsplit("METHINKS IT IS LIKE A WEASEL", ""))
Line 6,792 ⟶ 7,408:
parent= evolve(parent)
cat(paste0(parent, collapse=""), "\n")
}</
Line 6,804 ⟶ 7,420:
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
Line 6,842 ⟶ 7,458:
(printf "~s Total strings: ~s\n" C (for/sum ([n ns]) (* n 50))))
(for ([C (in-range 10 501 10)]) (try-run C 0.001))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|
<syntaxhighlight lang="raku"
constant @alphabet = flat 'A'..'Z',' ';
constant C =
sub mutate(Str $string, Real $mutate-chance where 0 ≤ * < 1) {
$string.subst: /<?{ rand < $mutate-chance }> . /, @alphabet.pick, :global
}
sub fitness(Str $string) { [+] $string.comb Zeq target.comb }
printf "\r%6d: '%s'", $++, $_ for
{ max :by(&fitness), mutate($
print "\n";
</syntaxhighlight>
=={{header|Red}}==
<
; allowed characters
Line 6,919 ⟶ 7,536:
]
print parent
</syntaxhighlight>
=={{header|REXX}}==
Line 6,930 ⟶ 7,547:
::* optimized for speed (only one random number/mutation)
::* supports an alphabet with lowercase letters and other letters and/or punctuation.
<
parse arg children MR seed . /*get optional arguments from the C.L. */
if children=='' | children=="," then children=10 /*# children produced each generation. */
Line 6,962 ⟶ 7,579:
else $= $ || substr(x , j , 1)
end /*j*/
return $</
{{out|output|text= when using the following input: <tt> 20 4% 11 </tt>}}
<pre>
Line 7,001 ⟶ 7,618:
<br>generating a random character ['''@.n'''] during mutation, thus making it slightly faster (about 10%),
<br>especially for a longer string and/or a low mutation rate.
<
parse arg children MR seed . /*get optional arguments from the C.L. */
if children=='' | children=="," then children=10 /*# children produced each generation. */
Line 7,040 ⟶ 7,657:
else $= $ || substr(x, m, 1)
end /*m*/
return $</
{{out|output|text= is the same as the previous version.}}
<br><br>
=={{header|Ring}}==
<
# Project : Evolutionary algorithm
Line 7,103 ⟶ 7,720:
next
return number(str)
</syntaxhighlight>
Output:
<pre>
Line 7,240 ⟶ 7,857:
{{trans|C}}
<
Charset = [" ", *"A".."Z"]
COPIES = 100
Line 7,278 ⟶ 7,895:
parent = copies.max_by {|c| fitness(c)}
end
log(iteration, rate, parent)</
{{out}}
Line 7,335 ⟶ 7,952:
=={{header|Rust}}==
<
//!
//! A simple evolutionary algorithm written in Rust.
Line 7,435 ⟶ 8,052:
c => c as char,
}
}</
{{out}}
<div style='height: 15em; overflow: scroll'><pre>
Line 7,470 ⟶ 8,087:
{{works with|Scala|2.8.1}}
<
case class LearnerParams(target:String,rate:Double,C:Int)
Line 7,506 ⟶ 8,123:
implicit val params = LearnerParams("METHINKS IT IS LIKE A WEASEL",0.01,100)
val initial = (1 to params.target.size) map(x => randchar) mkString
evolve(0,initial)</
=={{header|Scheme}}==
<
(import (scheme base)
(scheme write)
Line 7,568 ⟶ 8,185:
(display (string-append "Found: " parent "\n")))
(display parent) (newline))
</syntaxhighlight>
=={{header|Seed7}}==
<
const string: table is "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
Line 7,632 ⟶ 8,249:
incr(generation);
until best = 0;
end func;</
=={{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}}==
{{trans|C#}}
'''SequenceL Code:'''<br>
<
AllowedChars := " ABCDEFGHIJKLMNOPQRSTUVWXYZ";
Line 7,659 ⟶ 8,327:
fitnesses := Fitness(target, mutations);
in
mutations[firstIndexOf(fitnesses, vectorMax(fitnesses))];</
'''C++ Driver Code:'''<br>
<
#include <time.h>
#include "SL_Generated.h"
Line 7,711 ⟶ 8,379:
return 0;
}</
{{out}}
Line 7,798 ⟶ 8,466:
=={{header|Sidef}}==
{{trans|Raku}}
<
define mutate_chance = 0.08
define alphabet = [('A'..'Z')..., ' ']
Line 7,810 ⟶ 8,478:
parent != target;
parent = C.of{ mutate(parent) }.max_by(fitness)
) { printf("%6d: '%s'\n", i++, parent) }</
=={{header|Sinclair ZX81 BASIC}}==
Requires at least 2k of RAM. Displaying everything while it's running (generation count, parent, children, and their fitness scores) slows it down somewhat; but it would be very slow anyway, and it's nice to be able to look in on it from time to time and see how the program's getting along.
<
20 LET T$="METHINKS IT IS LIKE A WEASEL"
30 LET L=LEN T$
Line 7,856 ⟶ 8,524:
410 IF S$(K)=T$(K) THEN LET R=R+1
420 NEXT K
430 RETURN</
{{out}}
<pre> 349
Line 7,874 ⟶ 8,542:
=={{header|Smalltalk}}==
{{works with|GNU Smalltalk}}
<
<shape: #character>
Line 7,920 ⟶ 8,588:
randomLetter
[^Letters at: (Random between: 1 and: Letters size)]
]</
Use example:
<
QJUUIQHYXEZORSXGJCAHEWACH KG
QJUUIQHYXEZORSXGJCAHEWWCMSKG
Line 7,943 ⟶ 8,611:
METHINKS IW IS LIKE A WEASEL
METHINKS IT IS LIKE A WEASEL
Mutant</
=={{header|Swift}}==
Line 7,949 ⟶ 8,617:
{{trans|Rust}}
<
to target: String,
parent: inout String,
Line 8,003 ⟶ 8,671:
print("Gen 0: \(start) with fitness \(fitness(target: target, sentence: start))")
evolve(to: target, parent: &start, mutationRate: mutationRate, copies: 100)</
{{out}}
Line 8,032 ⟶ 8,700:
=={{header|Tailspin}}==
<
def alphabet: [' ABCDEFGHIJKLMNOPQRSTUVWXYZ'...];
def target: ['METHINKS IT IS LIKE A WEASEL'...];
Line 8,055 ⟶ 8,723:
otherwise
'Fitness $.fitness; at generation $@.generation;: "$.candidate...;"$#10;' -> !OUT::write
@.generation: $@.generation + 1"1";
1..$generationSize -> [$@.parent.candidate... -> \(
when <?(100 -> SYS::randomInt <..~$mutationPercent>)> do $randomCharacter!
Line 8,064 ⟶ 8,732:
[1..$target::length -> $randomCharacter] -> countFitness -> !evolve
</syntaxhighlight>
{{out}}
<pre>
Line 8,083 ⟶ 8,751:
{{works with|Tcl|8.5}}
{{trans|Python}}
<
# A function to select a random character from an argument string
Line 8,137 ⟶ 8,805:
}
puts ""
que</
Produces this example output:
<pre>#100 , fitness 42.9%, 'GSTBIGFS ITLSS LMD NNJPESZL'
Line 8,149 ⟶ 8,817:
===Alternate Presentation===
This alternative presentation factors out all assumption of what constitutes a “fit” solution to the <code>fitness</code> command, which is itself just a binding of the <code>fitnessByEquality</code> procedure to a particular target. None of the rest of the code knows anything about what constitutes a solution (and only <code>mutate</code> and <code>fitness</code> really know much about the data being evolved).
<
proc tcl::mathfunc::randchar {} {
# A function to select a random character
Line 8,218 ⟶ 8,886:
}
evolve $initial</
=={{header|uBasic/4tH}}==
This is a bit of a stretch, since uBasic/4tH doesn't support strings. Hence, the array is used to store the data.
<syntaxhighlight lang="text">T = 0 ' Address of target
L = 28 ' Length of string
P = T + L ' Address of parent
Line 8,329 ⟶ 8,997:
Proc _MutateDNA (P/L, P, 100) ' Now mutate the parent DNA
Return</
{{out}}
<pre>ZACXCLONTNTEAMJXYYFEP QQMDTA
Line 8,367 ⟶ 9,035:
takes about 500 iterations give or take 100.
<
#import nat
Line 8,386 ⟶ 9,054:
#cast %s
main = evolve parent</
output:
<pre>
Line 8,393 ⟶ 9,061:
=={{header|UTFool}}==
<syntaxhighlight lang="utfool">
···
http://rosettacode.org/wiki/Evolutionary_algorithm
Line 8,438 ⟶ 9,106:
generation◥
System.out.println "Target reached by generation #⸨generation⸩"
</syntaxhighlight>
=={{header|vbscript}}==
<
'This is the string we want to "evolve" to. Any string of any length will
'do as long as it consists only of upper case letters and spaces.
Line 8,539 ⟶ 9,207:
Private Function Random ( lower , upper )
Random = Int((upper - lower + 1) * Rnd + lower)
End Function</
Example output:
Line 8,572 ⟶ 9,240:
=={{header|Visual Basic}}==
Adapted from BBC Basic Code in this page. One diference from BBC Basic code is that in this code mutations are always good
<syntaxhighlight lang="visual basic">
Line 8,635 ⟶ 9,303:
FNfitness = F / Len(Text)
End Function
</syntaxhighlight>
Example output:
Line 8,665 ⟶ 9,333:
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">import rand
import rand.seed
const target = "METHINKS IT IS LIKE A WEASEL".bytes()
const set = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ".bytes()
fn initialize() []u8 {
rand.seed(seed.time_seed_array(2))
mut parent := []u8{len: target.len}
for i in 0..parent.len {
parent[i] = set[rand.intn(set.len) or {0}]
}
return parent
}
// fitness: 0 is perfect fit. greater numbers indicate worse fit.
fn fitness(a []u8) int {
mut h := 0
// (hamming distance)
for i, tc in target {
if a[i] != tc {
h++
}
}
return h
}
// set m to mutation of p, with each character of p mutated with probability r
fn mutate(p []u8, mut m []u8, r f64) {
for i, ch in p {
if rand.f64() < r {
m[i] = set[rand.intn(set.len) or {0}]
} else {
m[i] = ch
}
}
}
fn main() {
c := 20 // number of times to copy and mutate parent
mut parent := initialize()
mut copies := [][]u8{len: c, init: []u8{len: parent.len}}
println(parent.bytestr())
for best := fitness(parent); best > 0; {
for mut cp in copies {
mutate(parent, mut cp, .05)
}
for cp in copies {
fm := fitness(cp)
if fm < best {
best = fm
parent = cp.clone()
println(parent.bytestr())
}
}
}
}</syntaxhighlight>
{{out}}
<pre>Same as Go entry</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Option explicit
Function rand(l,u) rand= Int((u-l+1)*Rnd+l): End Function
Function fitness(i)
Dim d,j
d=0
For j=1 To lmod
If Mid(model,j,1)=Mid(cpy(i),j,1) Then d=d+1
Next
fitness=d
End Function
Sub mutate(i)
Dim j
cpy(i)=""
For j=1 To lmod
If Rnd<mut Then
cpy(i)=cpy(i)& Chr(rand(lb,ub))
Else
cpy(i)=cpy(i)& Mid(cpy(0),j,1)
End If
Next
End sub
Sub print(s):
On Error Resume Next
WScript.stdout.WriteLine (s)
If err= &h80070006& Then WScript.Echo " Please run this script with CScript": WScript.quit
End Sub
Dim model,lmod,ub,lb,c,cpy,fit,best,i,d,mut,cnt
model="METHINKS IT IS LIKE A WEASEL"
model=Replace(model," ","@")
lmod=Len(model)
Randomize Timer
ub=Asc("Z")
lb=Asc("@")
c=10
mut=.05
best=0
ReDim cpy(c)
For i=0 To lmod-1
cpy(best)=cpy(best)& chr(rand(lb,ub))
Next
best=0
cnt=0
do
cpy(0)=cpy(best)
fit=0
For i=1 To c
mutate(i)
d=fitness(i)
If d>fit Then fit=d:best=i
Next
cnt=cnt+1
If (fit=lmod) Or ((cnt mod 10)=0) Then print cnt &" " & fit & " "& Replace (cpy(best),"@"," ")
Loop While fit <>lmod
</syntaxhighlight>
{{out}}
<small>
<pre>
10 3 EATZ FMSHTCSEARSNKQBKI CJHXU
20 4 EETZGALSQTMREARSCKQBKIVQJHXA
30 6 METZ NLSQYMXO RSCKUBKLVQJHZA
40 8 METZ NWSQYMCO RSCKUTJVEETSM
50 10 METZ NWSQYTCO KHIKUTPVEEQSHH
60 10 METMKNWAEITCOIYAIKUTPVUEQSTC
70 11 METMKNWSEITCXIIJIKDXPVUEQSTE
80 13 METMLNWSEITCXI PIKDXPVWEWSTE
90 16 METMHNWSUITTXK LIKDXDVWEWSEL
....
1920 23 METHINKS ITNGS LIKZ AIWEASTL
1930 23 METHINKSMITVQS LIKE ANWEASDL
1940 24 METHINKSMITVQS LIKE AQWEASEL
1950 24 METHINKSZITVQS LIKE ADWEASEL
1960 24 METHINKSCITVOS LIKE ADWEASEL
1970 25 METHINKSTITVOS LIKE A WEASEL
1980 25 METHINKSZITJFS LIKE A WEASEL
1990 25 MFTHINKSZIT NS LIKE A WEASEL
2000 25 MFTHINKSZIT OS LIKE A WEASEL
2010 26 MITHINKSZIT IS LIKE A WEASEL
2020 26 MITHINKSZIT IS LIKE A WEASEL
2030 26 MITHINKSSIT IS LIKE A WEASEL
2040 26 MITHINKSSIT IS LIKE A WEASEL
2050 27 MQTHINKS IT IS LIKE A WEASEL
2058 28 METHINKS IT IS LIKE A WEASEL
</pre>
</small>
=={{header|Wren}}==
{{trans|Go}}
<
var target = "METHINKS IT IS LIKE A WEASEL"
Line 8,706 ⟶ 9,533:
}
}
}</
{{out}}
Line 8,742 ⟶ 9,569:
=={{header|XPL0}}==
<
string 0; \use zero-terminated convention (instead of MSb)
Line 8,810 ⟶ 9,637:
Iter:= Iter+1;
until Best = 0;
]</
Example output:
Line 8,830 ⟶ 9,657:
=={{header|zkl}}==
{{trans|D}}
<
const C = 100; // Number of children in each generation.
const P = 0.05; // Mutation probability.
Line 8,843 ⟶ 9,670:
.reduce(fcn(a,b){ if(fitness(a)<fitness(b)) a else b });
println("Gen %2d, dist=%2d: %s".fmt(gen+=1, fitness(parent), parent));
}while(parent != target);</
{{out}}
<pre>
|