• Contribute
• What's New
• Submit News

Purpose

When I started writing this article, I was going to make the series of lesson. But during writing, this article became one article by itself. So something strange is appeared in place. If you have enough time and enough perseverance, I want you to read through the whole article at first. And read again, then you can understand...I hope so.

Compiler

First

--- ga001.asm ---
	org 0100h
start:
; quit program.
	ret
--- ga001.asm ---

Compile

--- cut ---
nasm -f bin -o ga001.com ga001.asm
--- cut ---

Run

--- magic word ---
ga001
--- magic word ---

--- screen mimic ---
C:\gaasm>nasm -f bin -o ga001.com ga001.asm

C:\gaasm>ga001

C:\gaasm>
--- mimic is dead ---

Before making GENE pool

--- from Ralf's interupt list ---
AH = 00h

Return:
CX:DX = number of clock ticks since midnight
AL = midnight flag, nonzero if midnight passed since time last read
--- from Ralf's interupt list ---

--- randomize ---
;randomize   initialize rand seed
	xor ah,ah		; ah = 0
	int 1Ah			; get date and time
--- randomize ---

---XOR----
A | B | R
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
---XOR----

Feed seed:

--- feed seed ---
; dx is wide range
; cx is small...?
; so we take cx as 1st seed and dx as 2nd seed
	mov [seed1],cx		; save seed1
	mov [seed2],dx		; save seed2
--- feed seed ---

--- random generate ---
; generate random number
;  return
;	ax = number
random:
	db 0b8h	; mov ax,seed1
seed1:	db 0,0

	dec ax	; decrement
	
randloop:
	db 35h	; xor ax,seed2
seed2:	db 0,0
	inc ax	;
	xchg ah,al
	xor [seed2],ax	; 0.092
	sub ax,[seed1]
	rol al,1	; 0.091
	xchg ah,al	; 0.092
	sub [seed1],ax	; change seed1
	ret
--- random generate ---

Hi ppl, now we can generate any random number (I hope so ...) Finally, we stand the START line. Let's make GENE POOL !!

But before make GENE POOL, we have something to decide. Because what kind of gene expression we use is important. And it's depend on PROBLEM which we solve. Umm, making problem is harder than solve it :)...joke. I make 1 problem. It's a find the minimum value of fuction which has some Sin/Cos functions. I want to choose easy one. Everyone can understand where is the minimum, and if the function have LOCAL minimum is better. Exactly I don't have any idea of function's shape. So it's come back later. But I decide the range of search space between to 0 to 1. I make start line, only we need is the whistle ( NOT **'s whistler :-)

To make GENE POOL

--- something from 004 ---
POPULATION equ 100	; population of pool
--- end of c&p ---

--- this is pool maker ---
	mov cx,POPULATION * 4	; why multiply by 4 ? A gene have 4 byte (32 bit)!
	mov di,randnum
loop1:
	call random		; generate random number
	stosb			; we store the number which we generate to [di]
	loop loop1
--- this is pool maker ---

Evaluate

--- here's function ---
Rosenbrock's Saddle

F(x) = Sum(i=1,n) { 100*(x_(i+1)-x_i^2)^2 + (1-x_i)^2 } 

-2.048 .le. x_i .le. 2.048 

Minimum = 0.0 at x_i=1.0
This function has a long curved valley which is only slightly decreasing.
--- here's function ---

--- extract function ---
F(x) = Sum(i=1,n) { 100*(x_(i+1)-x_i^2)^2 + (1-x_i)^2 } 
     = { 100 * ( y - x ^ 2 ) ^ 2 + ( 1 - x ) ^ 2 } 
     + { 100 * ( x - y ^ 2 ) ^ 2 + ( 1 - y ) ^ 2 }
--- extract function ---

--- set up x ---
; setup x between -2048 to 2048
	fild dword [ range ]	; store denominator (4096, we need between 0 to 4096 )
	fild dword [ di ]	; get gene for x
	fabs			; absolute 'ST0'
	fprem			; 0 < 'ST0' < 4096
	fild dword [ rangef ]	; st0 = 2048, st1 = 0 < x < 4096
	fsubp st1,st0		; -2048 < 'ST0' < 2048
; setup x between -2.048 to 2.048
	fidiv word [ para2 ]
--- set up x ---

--- set up y ( x + 1 ) ---
; setup y between -2048 to 2048
	fild dword [ range ]	; store denominator (4096, we need between 0 to 4096 )
	fild dword [ di + 4 ]	; get gene for y
	fabs			; absolute 'ST0'
	fprem			; 0 < 'ST0' < 4096
	fild dword [ rangef ]	; st0 = 2048, st1 = 0 < y < 4096
	fsubp st1,st0		; -2048 < 'ST0' < 2048
; setup y between -2.048 to 2.048
	fidiv word [ para2 ]
--- set up y ---

--- division ---
	fabs			; absolute 'ST0'
	fdiv dword [ million ]	; ver 0.094
	fprem			; 0 < 'ST0' < 4096
--- division ---

--- datas ---
million:  dd 1000000.0
million2: dd 1000000
--- datas ---


--- code ---
	fld dword [ million ]
	fld dword [ million2 ]
--- code ---


--- result ---
st0=+1.401298E-0039 st1=+1.000000E+0006
--- result ---

--- pop ---
; pop two 4096(s)
	fxch st0,st3		; st0 ,st1 = 4096
	fcompp			; pop st0,st1
--- pop ---

--- calculate perm 1 ---
; we have st0 = x, st1 = y
; load x
	fld st0
; x^2
	fmul st0		; x^2
--- calculate perm 1 ---


--- calculate 2 ---
; load y
	fld st2
; y - x_i^2
	fsubrp st1
--- calculate 2 ---


--- calculate 3 ---
;( y - x ^ 2 ) ^ 2
	fmul st0
;100 * ( y - x ^ 2 ) ^ 2
	fimul word [ para1 ]
--- calculate 3 ---


--- calculate 4 ---
; 1 - x
	fld1
	fsub st2
; ( 1 - x ) ^ 2
	fmul st0
--- calculate 4 ---


--- calculate 5 ---
;{ 100 * ( y - x ^ 2 ) ^ 2 + ( 1 - x ) ^ 2 } 
	faddp st1
--- calculate 5 ---

--- calculate 6 ---
; load y
	fld st2
; y^2
	fmul st0		; y_i^2
; load x
	fld st2
; x - y^2
	fsubrp st1
;( y - x ^ 2 ) ^ 2
	fmul st0
;100 * ( y - x ^ 2 ) ^ 2
	fimul word [ para1 ]
; 1 - x
	fld1
	fsub st3
; ( 1 - x ) ^ 2
	fmul st0
;{ 100 * ( y - x ^ 2 ) ^ 2 + ( 1 - x ) ^ 2 } 
	faddp st1
--- calculate 6 ---

--- sum up & store ---
; store fitness to [si]
	fstp dword [si]
--- sum up & store ---

--- finalize ---
	fcompp
	ret 
--- finalize ---

Selection

Roulette Selection Algorithm.

--- gene size ---
GENESIZE equ 4
--- gene size ---

1. sum up the all fitness ( total )
2. make random number between 0 to total.
3. compare one's fitness and total
4. if one's fitness is less than total, total = total - fitness and goto 3
5. copy this indivisual to parent1
6. do the same 3 - 5 to make parent2

--- roulette selection initialize ---
selection:
; Roulette selection
; initialize
	fldz			; total
	mov di,fitness		; start address of fitness value
	mov cx,POPULATION	; number of POPULATION
--- roulette selection initialize ---

--- roulette selection 1 ---
; calculation total fitness
rouletteloop1:
	fld1			; 0.092
	fld dword [di]		; load fitness
	fdivp st1		; 0.092
	faddp st1		; sum up fitness
	add di,4		; to point next fitness
	loop rouletteloop1
--- roulette selection 1 ---

--- stack ---
before 'fld1'           - st(0) = 0
'fld1'                  - st(0) = 1, st(1) = 0
'fld dword [di]'        - st(0) = gene(0)'s fitness value, st(1) = 1 ,st(2) = 0
'fdivp st1'             - st(0) = a reciprocal of gene(0)'s fitness   ,st(1) = 0
'faddp st1'             - st(0) = a reciprocal of gene(0)'s fitness
--- stack ---

Next 'faddp st1' is done .
st(1) = st(1) + st(0), and pop st(0), so st(1) have nothing, st(0) have fitness value.

Then di = di + 4, so [di] indicates next genes fitness value.And loop .
When loop ends, st(0) have total fitness .
Next we make random number between 0 to total.

--- roulette selecion 2 ---
; roulette start
	call random		; generate random
	mov [ randtmp ], ax	; save random to temp
	fild dword [ randtmp ]	; load random number from temp
	fild dword [ randmax ]	; load maximum number of random
	fdivp st1		; st1 / st0 ( random / maximum ), this 
                                ; make 0 < random < 1
	fmul st1		; 0 < target < total fitness
--- roulette selecion 2 ---

--- FPU STACK is something like ... ---
call random		- st(0) = total fitness
mov [ randtmp ], ax	- st(0) = total fitness
fild dword [ randtmp ]	- st(0) = random number, st(1) = total fitness
fild dword [ randmax ]	- st(0) = RANDOM MAX   , st(1) = random number, 
                          st(2) = total fitness
fdivp st1		- st(0) = 0 < random < 1, st(1) = total fitness
fmul st1		- st(0) = 0 < random < total fitness, st(1) = total fitness
--- FPU STACK is something like ... ---

--- roulette selection before3 ---
; seek lucky adam
	mov cx,POPULATION	    ; number of POPULATION
	mov si,randnum - GENESIZE   ; start address of gene pool - GENESIZE (1 previous)
	mov di,fitness - 4	    ; start address of fitness value - 4 (1 previous)
--- roulette selection before3 ---

--- roulette selection 3 - 4 ---
rouletteloop2:
	add si, GENESIZE	; next gene
	add di,4		; next fitness
	fld1			; 0.092
	fld dword [di]		; load fitness
	fdivp st1		; 0.092
	fcom st1		; 
	fnstsw ax		; during st0 < st1 ,ah = ???????1. 
                                ; if st0 > st1 ah = ???????0
	and ah,1		; check condition
	fsubp st1,st0		; substract st1 - st0 and result store 
                                ; in st1 but 1 pop occur st0 have finally result 
	loopnz rouletteloop2	; cx = cx - 1. if cx isn't 0 but zeroflag is clear,
                                ; exit loop
--- roulette selection 3 - 4 ---

We met adam, so we want him to meet eve under the apple tree . So we pick up him from pool ( he can't swim well )

--- roulette selection 5 ---
; now [ si ] is adam's gene
	mov di, parent1		; here's seat for him
	mov cx, GENESIZE	; to copy gene, cx have genesize (byte)
	rep movsb		; do copy
	fcomp	st1		; adios adam
--- roulette selection 5 ---

--- maker ---
; making offspring loop
; init
	mov cx, POPULATION	; loop counter for  next generation
	mov di, offspring	; next swimmers warming up room
makeoffspring:
	push cx
	push di
	call selection		; selecti parents by ROULETTe alGo
	pop di
	call crossover		; corssover by uniform crossover
	add di, GENESIZE	; next position
	pop cx
	loop makeoffspring
--- maker ---

--- crossover ---
; uniform crossover
;   parent1, parent2 is gene
;   di = offsprring ( destination address )
; broken:
;	ax,bx,cx,dx
--- crossover ---

--- crossover 1 ---
crossover:
        xor bx,bx			; indicator ( counter ) reset
--- crossover 1 ---

--- crossover 1.5 ---
crossover0:
	mov cx,8			;1 byte is 8 bit.
--- crossover 1.5 ---

--- crossover 2 ---
crossover1:
        call random			; generate random number
        shr al,1			; check even or odd
        jc crossover2			; if odd (ie carry flag is set ), take parent2
        mov al, [ parent1 + bx ]	; because even, take parent1
        jmp crossover3			; go to set
crossover2:
        mov al, [ parent2 + bx ]	; take parent2
crossover3:
--- crossover 2 ---

--- crossover 3 ---
	shl al,cl			; shift al left by cl times
	rcr dl,1			; rotate dl including carry flag by 1
--- crossover 3 ---

--- crossover 4 ---
	loop crossover1			; cx = cx -1
--- crossover 4 ---

--- crossover 5 ---
	mov [di + bx],dl		; save it as gene
        inc bx
        cmp bx, GENESIZE
        jnz crossover0
--- crossover 5 ---

--- crossover 6 ---
	ret
--- crossover 6 ---

Mutation

--- mutationrate ---
mutationrate:	dd 0.001	; mutation rate
--- mutationrate ---

--- mutation initialize ---
; mutation
; di = offspring start address
mutation:
        xor bx,bx
mutation0:
        mov cx,8                ;1 byte is 8 bit.
--- mutation initialize ---

--- mutation 1 ---
	call random		; generate random
	mov [ randtmp ], ax	; save temp
	fld dword[ mutationrate ]	; load mutationrate
	fild dword [ randtmp ]	; load random number from temp
	fild dword [ randmax ]	; load maximum number of random
	fdivp st1		; st1 / st0, this make 0 < random < 1
--- mutation 1 ---

--- stack ---
fld dword[ mutationrate ] - st(0) = mutation rate
fild dword [ randtmp ]    - st(0) = random number, st(1) = mutation rate
fild dword [ randmax ]	  - st(0) = RAND_MAX, st(1) = random number st(2) = mutation rate
fdivp st1		- st(0) = random number / RNAD_MAX, st(1) = mutaion rate
--- stack ---

--- mutation 2 ---
	fcompp			; compare and pop st0 ,st1
	fnstsw ax		; during st0 < st1 ,ah = ???????1. if st0 > 
                                ; st1 ah = ???????0
	shr ah,1		; bit 0 of ah -> carry flag
	rcr dl,1		; save carry flag
        loop mutation1		; do this 1 byte( ie 8 times )
--- mutation 2 ---

--- mutation 3 ---
        xor [ di + bx ], dl	; Do MUTATION
--- mutation 3 ---

--- mutation 4 ---
        inc bx			; next position
        cmp bx,GENESIZE		; it's end?
        jnz mutation0		; if it's not end, we go back to 'mutation0'.
--- mutation 4 ---

MainLoop

--- mainloop 1 ---
; mainloop start
        mov cx, 10000   ; main loop counter
mainloop:
        push cx         ; save main loop counter 
--- mainloop 1 ---

--- mainloop 2 ---
; calculate all fitness
        mov cx, POPULATION
        mov di, randnum
        mov si, fitness
loop2:
        call evaluate
        add di, GENESIZE        ; ver 0.06
        add si,4
        loop loop2
--- mainloop 2 ---

--- mainloop 3 ---
; making offspring loop
; init
        mov cx, POPULATION      ; loop counter for  next generation
        mov di, offspring       ; next swimmer warming up room
makeoffspring:
        push cx
        push di
        call selection          ; selection by ROULETTe alGo
        pop di
        call crossover          ; corssover by uniform crossover
        call mutation           ; mutation
        add di, GENESIZE        ; next offspring's position
        pop cx
        loop makeoffspring
--- mainloop 3 ---

--- mainloop 4 ---
; judgement gene reach to goal ?
        pop cx			; load loop counter
        push cx			; save again
        cmp cx,1		; if the loop is end this time
        jnz changepool  	; if the loop is continued, go to next.
        call judgement		; search best fitness
--- mainloop 4 ---

--- mainloop 5 ---
; change gene to new.
changepool:
        mov di, randnum			; old gene pool
        mov si, offspring		; new gene are here.
        mov cx, POPULATION * GENESIZE	; size of pool
        rep movsb			; Do change
--- mainloop 5 ---

--- mainloop 6 ---
        pop cx			; counter is back
        loop mainlooop		; loop
--- mainloop 6 ---

Judgement

--- judgement initialize ---
; judgement
;  this version is to search minimum value of fitness.
;  return 
;       si = best gene address
;       dx = best fitness value address
judgement:
        mov bx, randnum			; bx = start address of gene
        mov si,bx			; si = bx
        mov di, fitness		; dx = start address of fitness value
        mov dx,di			; di = dx
        mov cx, POPULATION - 1		; cx is loop counter
        fld dword [ di ]		; first fitness is loaded
--- judgement initialize ---

--- judgement 1 ---
judgement1:
        add bx, GENESIZE                ; next gene
        add di, 4                       ; next fitness
        fld dword [ di ]                ; load fitness value
        fcom st1                        ; compare st0( current ) and st1 ( minimum )
        fnstsw ax			; st0 < st1 ,ah = ???????1. st0 > 
                                        ; st1 ah = ???????0
        shr ah,1			; check ah
        jnc judgement2
        mov dx,di                       ; save address of fitness value
        mov si,bx                       ; save address of gene
        fxch st0,st1			; exchange minimum value
judgement2:
        fcomp st1			; poped
        loop judgement1
        fcomp st1			; poped
        ret
--- judgement 1 ---

Tactics is following

1. we have the front gene's fitness value and gene address.
2. compare it to next gene's fitness and if next is smaller (higher) than it
   we have smaller (higher) one's fitness and gene address.
3. go to 1.

Conclusion?

Future Plan

• Make Smaller if only 1 byte and Speed up if can.
• Some problem in this article revealed will be fixed.
• I want this code run under pmode or something like that... to have wide range memory
• And I want to have SCRIPT LANGUAGE.
• Export to another platform.

• gaasm.zip - Source code and article (14.2Kb).