Post by tsh73 on Oct 4, 2022 22:19:26 GMT
Genetic algoritm, or GA
We already had some - but this one is really easy to explain/make/understand.
(it has a big drawback though - task at hand is easily solved without GA).
So.
Problem we are trying to solve:
we have unknowng string of digits of known length N
We need to guess it.
We can feed our guess g$ to a black box and get a number describing how good our guess is
(fitness function). Here we use function that returns number of "bulls" - in game "bulls and cows" (predessor of game Mastermind) number of digits happening to be on right places.
If fit(g$)=N we hit that secret string.
We keep population of candidates (guesses, that is, strings of digits)
on each "epoch" we
. apply fitness function over them
. sort by it and take only best ones
. generate new guesses by crossover
.. select parent1 "123456", parent2 "abcdef" (some digits I do not know now)
.. randomly select cross point, say 2
.. make new guess as left part of parent1 and right part of parent2, got "12cdef"
.. with some small probablility we randomly change one digit in a guess string
... - this keeps population from converging to single (and sometimes not optimal) value.
Algorithm ends if we found solution or number of iterations (epoch) is over.
Heavily commented.
We already had some - but this one is really easy to explain/make/understand.
(it has a big drawback though - task at hand is easily solved without GA).
So.
Problem we are trying to solve:
we have unknowng string of digits of known length N
We need to guess it.
We can feed our guess g$ to a black box and get a number describing how good our guess is
(fitness function). Here we use function that returns number of "bulls" - in game "bulls and cows" (predessor of game Mastermind) number of digits happening to be on right places.
If fit(g$)=N we hit that secret string.
We keep population of candidates (guesses, that is, strings of digits)
on each "epoch" we
. apply fitness function over them
. sort by it and take only best ones
. generate new guesses by crossover
.. select parent1 "123456", parent2 "abcdef" (some digits I do not know now)
.. randomly select cross point, say 2
.. make new guess as left part of parent1 and right part of parent2, got "12cdef"
.. with some small probablility we randomly change one digit in a guess string
... - this keeps population from converging to single (and sometimes not optimal) value.
Algorithm ends if we found solution or number of iterations (epoch) is over.
Heavily commented.
'genetic algorthim demo
'tsh73 October 2022
'guessing string of digits of length N
'fitness function is number of bulls in the guess string
'like in bulls and cows game.
global N, s$ 's$ is secret we did not supposed to know
N=10 'string length
'---------------------------------------------
'algorithm parameters
' population size
'popNum=100
popNum=1000
' survival rate. Only best got to breed
survRate=1/3
' children could mutate
'without mutation, it sometimes converges to non-optimal solution
'mutationProbability=0.1 'works better for pop 100
mutationProbability=0.03 '3%, works ok for pop 1000
maxEpoch=50 'maximum number of iterations we agreed to wait
dim p$(popNum) 'current population
dim fits(popNum,2) '1st is fit value, 2nd is number in p$
' (to be sorted by fit value, so second column would point to corresponding candidate solution)
dim newP$(popNum) 'next generation population
'---------------------------------------------
'initialisation
s$=mkRandString$() 'thing to search for
'radomly generate candidates
for i = 1 to popNum
p$(i)=mkRandString$()
next
'(not really needed but it shows what we start with)
'show first 10 candidates (they are random so fitness is low)
print "Initial population (first 10)"
print "To find: ";s$
for i = 1 to 10
print i, p$(i), fit(p$(i))
next
print "-----------------"
epoch=0
'=============================================
'genetic algorhithm iteration (one epoch)
while epoch<maxEpoch
epoch=epoch+1
print "Epoch ";epoch;" (best 10)"
'apply fitness function to population
for i = 1 to popNum
fits(i,1)=fit(p$(i))
'algorithm terminates if solution is found
if fits(i,1)=N then 'all digits on right places - solution
solution$ = p$(i)
'exit while
goto [endWhile] 'somehow line above did not compile
end if
fits(i,2)=i 'back link to p$(i) for sorting by fitness
next
'sort by fitness
sort fits(), popNum, 1, 1 'sort by col 1, reversed
'show best 10 candidates
print "To find: ";s$
for i = 1 to 10
print i, p$(fits(i,2)), fits(i,1)
next
print "-----------------"
'selection
'copy surviving (best part) to new population
survNum=int(popNum*survRate)
for i = 1 to survNum
newP$(i)= p$(fits(i,2))
next
'create rest of new population
for i = survNum+1 to popNum
'two random parents
parent1=int(1+rnd(1)*survNum)
parent2=int(1+rnd(1)*survNum)
'single-point crossover.
'Use 'use1' left digits from parent1,
'and rest from the right of parent2
use1=int(1+rnd(1)*(N-1)) '1..N-1
new$=left$(newP$(parent1),use1 ) + mid$(newP$(parent2),use1+1 )
'new candidates could mutate
if rnd(0)<mutationProbability then 'random digit in random place
pos=int(1+rnd(1)*N) '1..N
new$=left$(new$,pos-1) ;int(1+rnd(1)*10); mid$(new$,pos+1)
end if
newP$(i)= new$
next
'copy new population to current
for i = 1 to popNum
p$(i)= newP$(i)
next
wend
[endWhile]
if solution$<>"" then
print "Found solution in epoch ";epoch
else
print "Reached maximum epoch ";epoch
print "No solution found"
end if
input "-- Press Enter to quit --"; dummy$
'---------------------------------------------
function fit(g$) 'number of bulls in guess$
for i =1 to N
fit=fit+(mid$(s$,i,1)=mid$(g$,i,1))
next
end function
function mkRandString$()
for i = 1 to N
c=int(rnd(1)*10)
s1$=s1$;c
next
mkRandString$=s1$
end function
