Evolutionary algorithm: Difference between revisions
→{{header|jq}}
imported>Arakov |
|||
Line 4,441:
METHINKS IT IS LIKE A WEASEL
Ended in 240 generations
</pre>
=={{header|jq}}==
{{Works with|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>
<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):
(set|length) as $length
# 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 % $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
| (length * " ") 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":" "}
{"count":1,"string":" E AE LE "}
{"count":2,"string":" JE G WEAE LE W "}
{"count":3,"string":" ZJE G B WEAE QE WB"}
{"count":4,"string":" WDJE G BF T WEME QE WB"}
{"count":5,"string":" DWDJEIG BF NT WEME QE WI"}
{"count":6,"string":" IWDJEIA BF NT WEME QESQWI"}
{"count":7,"string":"JIWDJEIA BF NT WEME QESQWI"}
{"count":8,"string":"JIWDJEIA BF NT WEME C QESQWI"}
{"count":9,"string":"JIWDJEIA BV NT WEME C QESQBI"}
{"count":10,"string":"JIWDJEIA BV QT WEME C QEBQBR"}
...
{"count":90,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":91,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":92,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":93,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":94,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":95,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":96,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":97,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":98,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":99,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":100,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":101,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":102,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":103,"string":"METHJNKS IT IS LIKE A WEASEL"}
{"count":104,"string":"METHINKS IT IS LIKE A WEASEL"}
</pre>
| |||