Starting with:

 The target string: "METHINKS IT IS LIKE A WEASEL".
 An array of random characters chosen from the set of upper-case letters together with the space, and of the same length as the target string. (Call it the parent).
 A fitness function that computes the ‘closeness’ of its argument to the target string.
 A mutate function that given a string and a mutation rate returns a copy of the string, with some characters probably mutated.
 While the parent is not yet the target:
 copy the parent C times, each time allowing some random probability that another character might be substituted using mutate.
 Assess the fitness of the parent and all the copies to the target and make the most fit string the new parent, discarding the others.
 repeat until the parent converges, (hopefully), to the target.


See also

   Wikipedia entry:   Weasel algorithm.
   Wikipedia entry:   Evolutionary algorithm.

Note: to aid comparison, try and ensure the variables and functions mentioned in the task description appear in solutions



A cursory examination of a few of the solutions reveals that the instructions have not been followed rigorously in some solutions. Specifically,

 While the parent is not yet the target:
 copy the parent C times, each time allowing some random probability that another character might be substituted using mutate.
Note that some of the the solutions given retain characters in the mutated string that are correct in the target string. However, the instruction above does not state to retain any of the characters while performing the mutation. Although some may believe to do so is implied from the use of "converges"

(:* repeat until the parent converges, (hopefully), to the target.

Strictly speaking, the new parent should be selected from the new pool of mutations, and then the new parent used to generate the next set of mutations with parent characters getting retained only by not being mutated. It then becomes possible that the new set of mutations has no member that is fitter than the parent!

As illustration of this error, the code for 8th has the following remark.

Create a new string based on the TOS, changing randomly any characters which
don't already match the target:

NOTE: this has been changed, the 8th version is completely random now

Clearly, this algo will be applying the mutation function only to the parent characters that don't match to the target characters!

To ensure that the new parent is never less fit than the prior parent, both the parent and all of the latest mutations are subjected to the fitness test to select the next parent.




	bits	16
	cpu	8086
MRATE:	equ	26		; Mutation rate (MRATE/256)
COPIES:	equ	100		; Amount of copies to make
gettim:	equ	02Ch		; MS-DOS get time function
pstr:	equ	9		; MS-DOS print string
section	.text
	org	100h
	;;;	Use MS-DOS time to set random seed
	mov	ah,gettim
	int	21h
	mov	[rnddat],cx
	mov	[rnddat+2],dx
	;;;	Make first parent (random characters)
	mov	di,parent
	mov	cx,target.size-1
getchr:	call	rndchr		; Get random character
	stosb			; Store in parent
	loop	getchr
	mov	al,'$'		; Write string terminator
	stosb
	;;;	Main loop.
loop:	mov	bx,parent	; Print current parent
	mov	dx,bx
	call	puts
	call	fitnes		; Check fitness
	test	cl,cl		; If zero, we're done
	jnz	nxmut		; If not, do another mutation
	ret			; Quit to DOS
nxmut:	mov	dl,0FFh		; DL = best fitness yet
	mov	di,kids		; Set DI to start of memory for children
	mov	ch,COPIES	; CH = amount of copies to make
	xor	bp,bp
	;;;	Make copy, mutate, and test fitness
copy:	mov	bx,di		; Let BX = where next copy will go
	call	mutcpy		; Make the copy (and adjust DI)
	call	fitnes		; Check fitness
	cmp	cl,dl		; Is it better than the previous best one?
	ja	next		; If not, just do the next one,
	mov	dl,cl		; Otherwise, this is now the best one
	lea	bp,[di-target.size]	; Store a pointer to it in BP
next:	dec	ch		; One copy less
	jnz	copy		; Make another copy if we need to
	mov	si,bp		; We're done, the best child becomes
	mov	di,parent	; the parent for the next generation
	mov	cx,target.size
	rep	movsb
	jmp	loop		; Next generation
	;;;	Make copy of parent, mutating as we go, and store at [DI]
mutcpy:	mov	si,parent
.loop:	lodsb			; Get byte from parent
	stosb			; Store in copy
	cmp	al,'$'		; Is it '$'?
	je	.out		; Then we're done
	call	rand		; Otherwise, should we mutate?
	cmp	al,MRATE
	ja	.loop		; If not, do next character
	call	rndchr		; But if so, get random character,
	mov	[di-1],al	; and overwrite the current character.
	jmp	.loop		; Then do the next character.
.out:	ret
	;;;	Get fitness of character in [BX]
fitnes:	mov	si,target
	xor	cl,cl		; Fitness
.loop:	lodsb			; Get target character
	cmp 	al,'$'		; Done?
	je	.out		; Then stop
	cmp	al,[bx]		; Equal to character under [BX]?
	lahf			; Keep flags
	inc	bx		; Increment BX
	sahf			; Restore flags (was al=[bx]?)
	je	.loop		; If equal, do next character
	inc	cx		; Otherwise, count this as a mismatch
	jmp	.loop
.out:	ret
	;;;	Generate random character, [A-Z] or space.
rndchr:	call	rand		; Get random number
	and	al,31		; Lower five bits
	cmp	al,27		; One of 27 characters?
	jae	rndchr		; If not, get new random number
	add	al,'A'		; Make uppercase letter
	cmp	al,'Z'		; More than 'Z'?
	jbe	.out		; If not, it's OK
	mov	al,' '		; Otherwise, give a space
.out:	ret
	;;;	Random number generator using XABC algorithm
	;;;	Returns random byte in AL
rand:	push	cx
	push	dx
	mov	cx,[rnddat]	; CH=X CL=A
	mov	dx,[rnddat+2]	; DH=B DL=C
	inc	ch		; X++
	xor	cl,ch		; A ^= X
	xor	cl,dl		; A ^= C
	add	dh,cl		; B += A
	mov	al,dh		; C' = B 
	shr	al,1		; C' >>= 1
	xor	al,cl		; C' ^= A
	add	al,dl		; C' += C
	mov	dl,al		; C = C'
	mov	[rnddat],cx
	mov	[rnddat+2],dx
	pop	dx
	pop	cx
	ret
	;;;	Print string in DX, plus a newline, saving registers
puts:	push	ax
	push	dx
	mov	ah,pstr
	int	21h
	mov	dx,nl
	int	21h
	pop	dx
	pop	ax
	ret
section	.data
nl:	db	13,10,'$'
target:	db	'METHINKS IT IS LIKE A WEASEL$'
.size:	equ	$-target
section	.bss
rnddat:	resb	4		; RNG state
parent:	resb	target.size	; Place to store current parent
kids:	resb	COPIES*target.size	; Place to store children