Next: Technical Appendix: ECM Implementation Up: General (Behavior Based) Computational Previous: Run 12 Contents
The following version of an LCS system is able to play the game tic-tac-toe either as beginner or as opponent. It is a first prototype which will be investigated further in the future. It is part of a case study which shall clarify the basic concepts of LCSs applied to this game (see the chapters above for more information).
Usage: Start your scilab program (from www.scilab.org), copy this source code into the editor and save it as a program file. Then Load the program from the editor into scilab and start.
//**************************************************************
// File: LCS_v0.18.sce
// Authors: Gerd Doeben-Henisch
// Version Start: May-31, 2011
// Version Last: June-16, 2011
//******************************************************************
// Function: Implements a simple LCS according to Goldberg (1989)
// and some changes by GDH. Furthermore I constructed a complete new example
//
//*************************************************
// June-1,2011: More functions to support the game
//
//*************************************************
// June-2,2011: More functions to support the game
//
//*************************************************
// June-3,2011: Fitness function tttfitn()
//
//*************************************************
// June-4-9,2011: tttgameA2(), ttttournamentA2, ttttournamentA2history()
//
//**********************************************
// June-4,2011: Further improvements of the fitness function tttfitn(),
// rework of ainp() as binary Matrix, no string. Implementing the second player as
// separate unit with separate handling.
//
//*******************************************************
// June-12-13,2011: Completed evalDir() and tttfit2()
//
//*******************************************************
// June-14-16,2011: Extended the tournament functions in a way that
// the LCS system can also be a beginner
//
//*******************************************************
// Some helpful scilab-functions from the scilab libraries
//
// nancumsum ? This function returns the cumulative sum of the values of a matrix
// tabul ? frequency of values of a matrix or vector
// variance ? variance of the values of a vector or matrix
// strange ? range
// stdevf ? standard deviation (does need tabul)
// st_deviation (does not need additional functions)
// bin2dec := translate a binary string of '1','0' into a decimal number
// dec2bin
//
// SW-STRUCTURE
//
//****************************************************
//
// AGENTS
//
// Idea:
// An agent contains at least a set of classifiers. Classifiers have the compartments
// < IF THEN FIT >
// IF := state of world 9x2 Cells = 18 Cells
// THEN := action as a move (X,Y,O) 2+2+2 = 6 Cells
// FIT := fitness value as a 2 real values token and fraction 2 Cells
// Total length= 18 + 6 + 2 = 26 cells
// IF represents a possible input INP from the world,
// THEN represents a possible output OUT to the world and
// FIT represents an accumulated fitness value for this IF-THEN pair.
// The classifier can be encoded with integers which can be converted into
// other formats for processing.
//
CLASSIF1=[]
CLASSIF2=[]
AGENT1 = list(CLASSIF1)
AGENT2 = list(CLASSIF2)
//********************************************************
// Add a classifier
// classifNew()
//
// Idea:
// Given an input string and arandom classifier.
//Overwrite random classifier with input
// and generat possible move as well as minimal fitness
//
function [G]=classifNew(INP,X,Y,F,show)
li =length(INP)
lp = 26
[P]=popgen(1,lp)
G=zeros(1,lp) //new classifier
for i=1:li
G(1,i) = INP(1,i),
end
for i = li+1:lp
G(1,i) = P(1,i),
end
//inserts random move (X,Y,O)
if show == 1 then disp('X='), disp(X), disp('Y='), disp(Y), end
x=dec2bin(X)
if length(x) == 1 then x= '0'+x, //strsplit() needs at least two signs...
end
xx=strsplit(x)'
for i=1:2
if xx(1,i) == '1' then G(1,li+i)=1, else G(1,li+i)=0,
end
end
y=dec2bin(Y)
if length(y) == 1 then y= '0'+y,
end
yy=strsplit(y)'
for i=1:2
if yy(1,i) == '1' then G(1,li+2+i)=1, else G(1,li+2+i)=0,
end
end
G(1,li+5) = 1
G(1,li+6) = 0
//generate fitness
G(1,lp-1)= F //depends from scenario
G(1,lp) = 0 // Fraction has to computed from overall system
endfunction
//********************************************************
// Add a classifier
// classifNew2()
//
// Idea:
// Only difference the assumption of the set CLASSIF to have more columns
// c = l+p = 24+7
// r,c := row/col of CLASSIF because CLASSIF can be extended by genetic operators
// CLASSIF
// 1-18 := board content
// 19-20 := X
// 21-22 := Y
// 23-24 := O
// l := 24
// p := 7
// l+1 := F
//
// Input:
// r,c := row/col of CLASSIF
function [G]=classifNew2(INP,X,Y,F,r,c,show)
l=24
p=7
li =length(INP)
[P]=popgen(1,c)
G=zeros(1,c) //new classifier
if show==4 then
disp('classifNew2: Before G with INP')
disp('INP='), disp(INP)
disp('CLASSIF='),disp(CLASSIF)
disp('rr ='), disp(r), disp('cc='),disp(c)
end
for i=1:li
G(1,i) = INP(1,i),
end
for i = li+1:c
G(1,i) = P(1,i),
end
//inserts random move (X,Y,O)
x=dec2bin(X)
if length(x) == 1 then x= '0'+x, //strsplit() needs at least two signs...
end
xx=strsplit(x)'
for i=1:2
if xx(1,i) == '1' then G(1,li+i)=1, else G(1,li+i)=0,
end
end
y=dec2bin(Y)
if length(y) == 1 then y= '0'+y,
end
yy=strsplit(y)'
for i=1:2
if yy(1,i) == '1' then G(1,li+2+i)=1, else G(1,li+2+i)=0,
end
end
//generate fitness
G(1,l+1)= F //depends from scenario
G(1,l+2) = 0 // Fraction has to computed from overall system
if show==4 then
disp('classifNew2: After G with F'), disp(G)
end
endfunction
//*************************************************
// Get (X,Y) out of classifier
// getXY()
//
function [X,Y]=getXY(MROW)
//Transforms row of matrix into a vector
v=MROW(1,:)
//takes the section with the X-binaries
[X]= vec22dec(v,19,20)
if X == 0 then X+1,
end
//takes the section with the y-binaries
[Y]= vec22dec(v,21,22)
if Y == 0 then Y+1,
end
endfunction
//***********************************************************
// Playlist with n-many players
//
function [PList]=plistgen(n)
PList=[1:1:n]
endfunction
//*********************************************
// PMatrix for n x n players
//
function [PMatrix]=pmatrixgen(PList)
n=length(PList)
PMatrix=zeros(n+1, n+1)
for i=2:n+1
PMatrix(1,i)=i-1
PMatrix(i,1)=i-1
end
endfunction
//*********************************************
// PMatrix for n x n players
//
// Input:
// N := number of games betwin random beginner 'X' and opponent 'O' with classifiers
function [PMatrix]=pmatrixgenA2(N)
PMatrix=zeros(N+1, 3)
PMatrix(1,2)=1,
PMatrix(1,3)=2,
for i=2:N+1
PMatrix(i,1)=i-1
end
endfunction
//*********************************************
// Action generator
//
// Output:
// X,Y,O := an action consist of a cell-vector and a 'piece' in {'X','O'}
// The cell-vector is (x,y) with x,y in {1,2,3}
// P := Player; 1 := Beginner, 2 := Opponent
function [X,Y,O]=tttaction0(P)
X=0
while X==0
X=round(rand()*3)
end
Y=0
while Y==0
Y=round(rand()*3)
end
if P==1 then O='X', else O='O', end
endfunction
//*********************************************
// Action generator insertion and check whether cell free and right turn
//
// Idea:
// Checks whether a planned cell is free and checks which piece has to be played
// If number of different pieces is equal, then 'X' is needed, otherwise 'O'
//
// Input:
// W := World as Board
// X,Y := cell coordinates
// O := Piece to be placed {'X','O'}
//
// Output:
// ALLOW := Whether cell is free or not {0,1}
// W := World after insertion
function [W,ALLOW]=tttaction1(W,X,Y,O,show)
[r,c]=size(W)
ALLOW = 1
// Check which piece
PIX=0, PIO=0
for i=1:r
for j=1:c
if W(i,j)=='X' then PIX=PIX+1,
elseif W(i,j)=='O' then PIO=PIO+1
end
end
end
if show == 1 then disp('PIX = '), disp(PIX), disp('PIO = '), disp(PIO), end
if PIX == PIO & O <> 'X' then ALLOW=0,
if show == 1 disp('X should move but does not '), end,
elseif PIX > PIO & O <> 'O' then ALLOW = 0,
if show == 1 disp('O should move but does not '), end,
end
// Check cell free
if ALLOW == 1 then
if W(X,Y) <> '_' then ALLOW = 0,
else ALLOW = 1,
W(X,Y) = O,
end
if show == 1 disp('Cell free = '), disp(ALLOW), end
end
endfunction
//*********************************************
// Action generator insertion and checks only whether cell free
//
// Idea:
// Checks whether a planned cell is free
//
// Input:
// W := World as Board
// X,Y := cell coordinates
// O := Piece to be placed {'X','O'}
//
// Output:
// ALLOW := Whether cell is free or not {0,1}
// W := World after insertion
function [W,ALLOW]=tttaction1b(W,X,Y,O,show)
[r,c]=size(W)
// Check cell free
if W(X,Y) <> '_' then ALLOW = 0,
else ALLOW = 1,
W(X,Y) = O,
end
if show == 1 disp('Cell free = '), disp(ALLOW), end
endfunction
//*********************************************
// Free Cell Generator
// freeCellIndex()
//
// Idea:
// receives a list of free cells CLst
// and computes randomly an index for a free cell
//
// Input:
// N := number of free cells
//
// Output:
// K := index for free cell
//
function [K]=freeCellIndex(N)
K=0
while K==0
K=round(rand()*N)
end
endfunction
//**************************************+
// diagIn()
// Inverse diagonale of a quadratic matrix
// Inverse to scilab function diag()
//
// Input:
// M := matrix
//
// Output:
// D := the right-left-diagonal values as 1-col matrix
//
// Attention: scilab uses (Y,X) notation!!!!
function [D]=diagIn(M)
[r,c]=size(M)
D=[]
if r <> c then error('No Quadratic Matrix in diagIn()'), end
for i=1:r
D(i,1) = M(i,r+1-i)
end
endfunction
//*********************************************
// Check whether the game is ended
//
// Idea:
// Check whether in a row or column or diagonale three pieces of one player are placed
//
// Input:
// W := World as Board
//
// Output:
// END := Whether game has ended or not {0,1}
// PLAYER := Which player has won {'X','O'}
function [PLAYER,END]=endgame(W,show)
[r,c]=size(W)
END = 0
// Check diagonales
[D]=diag(W)
PIX=0, PIO=0
for i=1:r
if D(i,1) == 'X' then PIX=PIX+1,
elseif D(i,1) == 'O' then PIO=PIO+1,
end
end
if show ==1 then disp('diag D= '),disp(D), disp(PIX), disp(PIO),end
if PIX == 3 then END=1, PLAYER= 'X',
elseif PIO == 3 then END=1, PLAYER= 'O',
else END=0, PLAYER='_'
end
if END == 0 then
[D]=diagIn(W)
PIX=0, PIO=0
for i=1:r
if D(i,1) == 'X' then PIX=PIX+1,
elseif D(i,1) == 'O' then PIO=PIO+1,
end
end
if show ==1 then disp('diag D= '),disp(D), disp(PIX), disp(PIO),end
if PIX == 3 then END=1, PLAYER= 'X',
elseif PIO == 3 then END=1, PLAYER= 'O',
else END=0, PLAYER='_'
end
end
// check Rows
if END == 0 then
i=1
while i < r+1 & END == 0
[D]=W(i,:)
if show ==1 then disp('Row D= '),disp(D),end
PIX=0, PIO=0
j=1
while j < r+1
if D(1,j) == 'X' then PIX=PIX+1,
elseif D(1,j) == 'O' then PIO=PIO+1,
end
j=j+1
end // while j
if show ==1 then disp('PIX, PIO = '), disp(PIX), disp(PIO),end
if PIX == 3 then END=1, PLAYER= 'X',
elseif PIO == 3 then END=1, PLAYER= 'O',
else END=0, PLAYER='_'
end // if PIX
i=i+1
end //while i
end //if END
// Check Columns
if END == 0 then
i=1
while i < r+1 & END == 0
[D]=W(:,i), D=D'
if show ==1 then disp('Column (rotated) D= '),disp(D),end
PIX=0, PIO=0
j=1
while j < r+1
if D(1,j) == 'X' then PIX=PIX+1,
elseif D(1,j) == 'O' then PIO=PIO+1,
end
j=j+1
end // while j
if show ==1 then disp('PIX, PIO = '), disp(PIX), disp(PIO),end
if PIX == 3 then END=1, PLAYER= 'X',
elseif PIO == 3 then END=1, PLAYER= 'O',
else END=0, PLAYER='_'
end // if PIX
i=i+1
end //while i
end //if END
endfunction
//****************************************************
// Free cells for a move
// freeCells()
//
// Idea:
// All free sells are listet for the generation of a possible move
//
// Input:
// W := world state
//
// Output:
// CLst := List of all cells with those which are free
//
function [CLst]=freeCells(W,show)
[r,c]=size(W)
CLst=[]
//reading the world matrix and generate the list
k=0
for i=1:r
for j=1:c
if show==1 then disp(i), disp(j), disp('W(i,j)'), disp(W(i,j)), end
if W(i,j)== '_' then k=k+1, CLst(k,1)=i, CLst(k,2)=j
if show==1 then disp('k ='), disp(k), disp('CLst k 1 2 ='), disp(CLst(k,1)), disp(CLst(k,2)), end
end //end if empty
end //end for j
end //end for i
endfunction
//****************************************************
// Input function for an agent ainp()
//
// Idea:
// The actual state of the world together with the fitness value for the last action
// is delivered to the agent. This is done with a vector.
function [INP]=ainp(W,FIT)
[r,c]=size(W)
//reading the world matrix and encode the cells
for i=1:r
for j=1:c
if W(i,j)== 'X' then WI(i,j)='01',
elseif W4(i,j)== 'O' then WI(i,j)='10',
else WI(i,j)='00',
end,
end,
end
//Concatenating the partial strings into one string INP
INP=''
for i=1:r
for j=1:c
INP = INP + WI(i,j),
end,
end
//Concatenating the fitness value
INP=INP+':'+dec2bin(FIT)
endfunction
//****************************************************
// Input function for an agent ainp() (as matrix)
//
// Idea:
// The actual state of the world is delivered to the agent. This is done with a line matrix.
//
// Input:
// W := World state
//
// Output:
// INP := Matrix with binary code of world and fitness
function [INP]=ainp2(W)
[r,c]=size(W)
l=2*c
INP=zeros(1,l)
//reading the world matrix and encode the cells
k=1
for i=1:r
for j=1:c
if W(i,j)== 'X' then INP(1,k)=0, INP(1,k+1)=1,
elseif W(i,j)== 'O' then INP(1,k)=1, INP(1,k+1)=0,
else INP(1,k)=0, INP(1,k+1)=0,
end,
k=k+2
end,
end
endfunction
//*********************************************
// Fitness function for tic-tac-toe
// tttfitn()
//
// Idea:
// The player makes a move (X,Y,O)
// The following cases have to be evaluated:
// The new piece will be evaluated in every direction whether it
// has n-many pieces in one direction without a piece of the opoonent.
// This can be controlled by flags FLAG=[1,2,3,4,5]
// 1 : allowness
// 2 : rows
// 3 : columns
// 4 : diagonales LR
// 5 : diagonales RL
//
// Input:
// W := World as Board
// X,Y := cell coordinates //Attention: scilab uses internally M(Y,X) !!!!!!
// O := Piece to be placed {'X','O'}
//
// Output:
// F := fitness values
// FLAG := for control reasons
// ALLOW := allownes
// W := world to show final state
//
// Style : The actual code is not very elegant. It should be improved using more abstract
// topological predicates implemented as basic operators.
function [F,FLAG, ALLOW,W]=tttfitn(W,X,Y,O,show)
if show == 1 then disp('X,Y,O ='), disp(X), disp(Y), disp(O), end
[r,c]=size(W)
ROW =[0,0,0]
COL=[0,0,0]
DIAL=[0,0,0]
DIAR =[0,0,0]
FLAG = [0 0 0 0 0] // Allowness, Row, Col, Dia-LR, Dia-RL
//*******************************
// Check allowness
if W(Y,X) == '_' then FLAG(1,1)=1, ALLOW=1, W(Y,X) = O,
else ALLOW = 0,
end
//*****************************************
//Check neighborship, 3 cases (center, corner, middle)
// with subcases
if X == 2 & Y == 2 then C=1,
elseif (X == 1 & Y == 1) then C=2,
elseif (X == 3 & Y == 1) then C=3,
elseif (X == 3 & Y == 3) then C=4,
elseif (X == 1 & Y == 3) then C=5,
elseif (X == 2 & Y == 1) then C=6,
elseif (X == 3 & Y == 2) then C=7,
elseif (X == 2 & Y == 3) then C=8,
elseif (X == 1 & Y == 2) then C=9
end
if show == 1 then disp('C = '), disp(C), end
select C
//****************************************
// 1) Check Center
case 1 then
if show == 1 then disp('Case Center'), end
//Place piece first
ROW =[0,1,0]
COL=[0,1,0]
DIAL=[0,1,0]
DIAR =[0,1,0]
// Search context
// Counts only if the missing cell in one direction is free!
if W(Y-1,X) == 'X' | W(Y+1,X) == 'X' then COL(1,2)=0,
elseif W(Y-1,X) == 'O' & W(Y+1,X) == 'O' then COL(1,3)=1,COL(1,1)=1,
elseif W(Y-1,X) == 'O' | W(Y+1,X) == 'O' then COL(1,1)=1,
end,
if W(Y-1,X+1) == 'X' | W(Y+1,X-1) == 'X' then DIAR(1,2)=0,
elseif W(Y-1,X+1) == 'O' & W(Y+1,X-1) == 'O' then DIAR(1,1)=1,DIAR(1,3)=1,
elseif W(Y+1,X-1) == 'O' | W(Y+1,X+1) == 'O' then DIAR(1,3)=1,
end,
if W(Y,X+1) == 'X' | W(Y,X-1) == 'X' then ROW(1,2)=0
elseif W(Y,X+1) == O & W(Y,X-1) == 'O' then ROW(1,3)=1, ROW(1,1)=1,
elseif W(Y,X-1) == O | W(Y,X+1) == 'O' then ROW(1,1)=1,
end,
if W(Y+1,X+1) == 'X' | W(Y-1,X-1) == 'X' then DIAL(1,2)=0,
elseif W(Y+1,X+1) == O & W(Y-1,X-1) == 'O' then DIAL(1,3)=1,DIAL(1,1)=1,
elseif W(Y-1,X-1) == O | W(Y+1,X+1) == 'O' then DIAL(1,1)=1,
end,
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
disp('DIAL'), disp(DIAL),
disp('DIAR'), disp(DIAR),
end
// Compute fitness
R=sum(ROW)
CL=sum(COL)
DL=sum(DIAL)
DR=sum(DIAR)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
FLAG(1,4)=DL
FLAG(1,5)=DR
//****************************************
// 2) Check Corner
case 2 then
//****************************************
// 2.1) Check Left Upper Corner
if show == 1 then disp('Case LU Corner'), end
//Place piece first
ROW =[1,0,0]
COL=[1,0,0]
DIAL=[1,0,0]
// Search context
if W(Y+1,X) == 'X' | W(Y+2,X) == 'X' then COL(1,1)=0,
elseif W(Y+1,X) == 'O' & W(Y+2,X) == O then COL(1,3)=1,COL(1,2)=1,
elseif W(Y+1,X) == O | W(Y+2,X) == O then COL(1,2)=1,
end
if W(Y+1,X+1) == 'X' | W(Y+2,X+2) == 'X' then DIAL(1,1)=0,
elseif W(Y+1,X+1) == 'O' & W(Y+2,X+2) == O then DIAL(1,3)=1, DIAL(1,2)=1,
elseif W(Y+1,X+1) == O | W(Y+2,X+2) == O then DIAL(1,2)=1,
end
if W(Y,X+1) == 'X' | W(Y,X+2) == 'X' then ROW(1,1)=0,
elseif W(Y,X+1) == O & W(Y,X+2) == O then ROW(1,3)=1,ROW(1,2)=1
elseif W(Y,X+1) == 'O' | W(Y,X+2) == O then ROW(1,3)=1,
end
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
disp('DIAL'), disp(DIAL),
end
R=sum(ROW)
CL=sum(COL)
DL=sum(DIAL)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
FLAG(1,4)=DL
case 3 then
//****************************************
// 2.2) Check Right Upper Corner
if show == 1 then disp('Case RU Corner'), end
//Place piece first
ROW =[0,0,1]
COL=[1,0,0]
DIAR=[1,0,0]
// Search context
if W(Y+1,X) == 'X' | W(Y+2,X) == 'X' then COL(1,1)=0,
elseif W(Y+1,X) == O & W(Y+2,X) == O then COL(1,2)=1,COL(1,3)=1,
elseif W(Y+1,X) == 'O' | W(Y+2,X) == O then COL(1,3)=1,
end
if W(Y+1,X-1) == 'X' | W(Y+2,X-2) == 'X' then DIAR(1,1)=0,
elseif W(Y+1,X-1) == O & W(Y+2,X-2) == O then DIAR(1,2)=1, DIAR(1,3)=1,
elseif W(Y+1,X-1) == 'O'| W(Y+2,X-2) == O then DIAR(1,3)=1,
end
if W(Y,X-1) == 'X' | W(Y,X-2) == 'X' then ROW(1,3)=0,
elseif W(Y,X-1) == O & W(Y,X-2) == O then ROW(1,1)=1,ROW(1,2)=1
elseif W(Y,X-1) == 'O' | W(Y,X-2) == O then ROW(1,1)=1,
end
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
disp('DIAR'), disp(DIAR),
end
R=sum(ROW)
CL=sum(COL)
DR=sum(DIAR)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
FLAG(1,5)=DR
case 4 then
//****************************************
// 2.3) Check Right Down Corner
if show == 1 then disp('Case RD Corner'), end
//Place piece first
ROW =[0,0,1]
COL=[0,0,1]
DIAL=[0,0,1]
// Search context
if W(Y-1,X) == 'X' | W(Y-2,X) == 'X' then COL(1,3)=0,
elseif W(Y-1,X) == O & W(Y-2,X) == O then COL(1,2)=1,COL(1,1)=1,
elseif W(Y-1,X) == 'O' | W(Y-2,X) == O then COL(1,1)=1,
end
if W(Y-1,X-1) == 'X' | W(Y-2,X-2) == 'X' then DIAL(1,3)=0,
elseif W(Y-1,X-1) == O & W(Y-2,X-2) == O then DIAL(1,1)=1, DIAL(1,3)=1,
elseif W(Y-1,X-1) == 'O' | W(Y-2,X-2) == O then DIAL(1,1)=1,
end
if W(Y,X-1) == 'X' | W(Y,X-2) == 'X' then ROW(1,3)=0,
elseif W(Y,X-1) == O & W(Y,X-2) == O then ROW(1,1)=1,ROW(1,2)=1
elseif W(Y,X-1) == 'O' | W(Y,X-2) == O then ROW(1,1)=1,
end
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
disp('DIAL'), disp(DIAL),
end
R=sum(ROW)
CL=sum(COL)
DL=sum(DIAL)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
FLAG(1,4)=DL
case 5 then
//****************************************
// 2.4) Check left down corner
if show == 1 then disp('Case LD Corner'), end
//Place piece first
ROW =[1,0,0]
COL=[0,0,1]
DIAR=[0,0,1]
// Search context
if W(Y-1,X) == 'X' | W(Y-2,X) == 'X' then COL(1,3)=0,
elseif W(Y-1,X) == O & W(Y-2,X) == O then COL(1,2)=1,COL(1,1)=1,
elseif W(Y-1,X) == 'O' | W(Y-2,X) == O then COL(1,1)=1,
end
if W(Y-1,X+1) == 'X' | W(Y-2,X+2) == 'X' then DIAR(1,3)=0,
elseif W(Y-1,X+1) == O & W(Y-2,X+2) == O then DIAR(1,2)=1, DIAR(1,1)=1,
elseif W(Y-1,X+1) == 'O' | W(Y-2,X+2) == O then DIAR(1,1)=1,
end
if W(Y,X+1) == 'X' | W(Y,X+2) == 'X' then ROW(1,1)=0,
elseif W(Y,X+1) == O & W(Y,X+2) == O then ROW(1,3)=1,ROW(1,2)=1
elseif W(Y,X+1) == 'O' | W(Y,X+2) == O then ROW(1,3)=1,
end
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
disp('DIAR'), disp(DIAR),
end
R=sum(ROW)
CL=sum(COL)
DR=sum(DIAR)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
FLAG(1,5)=DR
//*****************************************
// 3) Check Middle of Boarder
case 6 then
//*****************************************
// 3.1) Check Middle Upper Boarder
if show == 1 then disp('Case MU BOARDER'), end
//Place piece first
ROW =[0,1,0]
COL=[1,0,0]
// Search context
if W(Y,X-1) == 'X' | W(Y,X+1) == 'X' then ROW(1,2)=0,
elseif W(Y,X-1) == O & W(Y,X+1) == O then ROW(1,1)=1,ROW(1,3)=1
elseif W(Y,X-1) == 'O'| W(Y,X+1) == O then ROW(1,3)=1,
end
if W(Y+1,X) == 'X' | W(Y+2,X) == 'X' then COL(1,1)=0,
elseif W(Y+1,X) == O & W(Y+2,X) == O then COL(1,2)=1,COL(1,3)=1,
elseif W(Y+1,X) == 'O' | W(Y+2,X) == O then COL(1,3)=1,
end
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
end
R=sum(ROW)
CL=sum(COL)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
case 7 then
//*****************************************
// 3.2) Check Middle Right Boarder
if show == 1 then disp('Case MR BOARDER'), end
//Place piece first
ROW =[0,0,1]
COL=[0,1,0]
// Search context
if W(Y,X-1) == 'X' | W(Y,X-2) == 'X' then ROW(1,3)=0,
elseif W(Y,X-1) == O & W(Y,X-2) == O then ROW(1,1)=1,ROW(1,2)=1
elseif W(Y,X-1) == 'O'| W(Y,X-2) == O then ROW(1,1)=1,
end
if W(Y+1,X) == 'X' | W(Y-1,X) == 'X' then COL(1,2)=0,
elseif W(Y+1,X) == O & W(Y-1,X) == O then COL(1,1)=1,COL(1,3)=1,
elseif W(Y+1,X) == 'O' | W(Y-1,X) == O then COL(1,1)=1,
end
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
end
R=sum(ROW)
CL=sum(COL)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
case 8 then
//*****************************************
// 3.3) Check Middle Down Boarde
if show == 1 then disp('Case MD BOARDER'), end
//Place piece first
ROW =[0,1,0]
COL=[0,0,1]
// Search context
if W(Y,X-1) == 'X' | W(Y,X+1) == 'X' then ROW(1,2)=0,
elseif W(Y,X-1) == O & W(Y,X+1) == O then ROW(1,1)=1,ROW(1,3)=1
elseif W(Y,X-1) == 'O' | W(Y,X+1) == O then ROW(1,3)=1,
end
if W(Y-1,X) == 'X' | W(Y-2,X) == 'X' then COL(1,3)=0,
elseif W(Y-1,X) == O & W(Y-2,X) == O then COL(1,2)=1,COL(1,1)=1,
elseif W(Y-1,X) == 'O'| W(Y-2,X) == O then COL(1,1)=1,
end
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
end
R=sum(ROW)
CL=sum(COL)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
case 9 then
//*****************************************
// 3.4) Check Middle Left Boarde
if show == 1 then disp('Case ML BOARDER'), end
//Place piece first
ROW =[1,0,0]
COL=[0,1,0]
// Search context
if W(Y,X+1) == 'X' | W(Y,X+2) == 'X' then ROW(1,1)=0,
elseif W(Y,X+1) == O & W(Y,X+2) == O then ROW(1,3)=1,ROW(1,2)=1,
elseif W(Y,X+1) == 'O' | W(Y,X+2) == O then ROW(1,3)=1,
end
if W(Y+1,X) == 'X' | W(Y-1,X) == 'X' then COL(1,2)=0,
elseif W(Y+1,X) == O & W(Y-1,X) == O then COL(1,1)=1,COL(1,3)=1,
elseif W(Y+1,X) == 'O' | W(Y-1,X) == O then COL(1,1)=1,
end
if show == 1 then disp('ROW'), disp(ROW),
disp('COL'), disp(COL),
end
R=sum(ROW)
CL=sum(COL)
FLAG(1,1)=ALLOW
FLAG(1,2)=R
FLAG(1,3)=CL
else break
end //select
if show == 1 then disp('FLAG Final'), disp(FLAG), end
// Compute final fitness value
F=0
for k=2:5
if FLAG(1,k) > F then F=FLAG(k),end
end
F=F*5 //Enhancing the differences between the cases
endfunction
//****************************************************
// Match a line L with a matrix M
//
// Idea:
// Start comparison of line L with matrix M.
// Every time there is a match the results matrix TX will notify a '1'
function [TX]=mmmatch(L,M)
[r,c]=size(M)
TX=ones(r,1)
l=length(L)
for i=1:r
for j=1:l
if L(1,j)<>M(i,j) then TX(i,1)=0, break,
end //if <>
end //for j
end //for i
endfunction
//*************************************
// Evaluation of a dirction
// evalDir()
//
// Idea:
// Take a direction of a world state w_i of world W with n=length
// Direction is row, column or diagonal
// Look for a certain player P in {'X', 'O'}
// Count the piecesm of this player if there are no pieces of the opponent
// Every dimension counts as 1
// Every dimension with m >= round(n/2)+1)-many pieces receives m times a bonus additionally
//
// Input:
// W := World as Board
// DIM := Which kind of dimension {R,C,L,D}, Row, Columns, LR diagonal, RL diagonal
// INDEX := within W row or colum or 1 := DL or n = DR
// P := type of player, 'X' := Beginner, 'O' := opponent
//
// Output:
// M := Number of pieces in that dimension with no opponent
// BONUS := If m >= round(n/2)+1) then m (times a bonus)
//
// Computation:
// Go through a dimension DIM and count the pieces
function [M,BONUS]=evalDir(W,DIM,IND,P,show)
[r,c]=size(W)
M=0 //Counter for player
MM=0 //Flag for opponent
BONUS=0
if P == 'X' then PP = 'O', else PP='X', end //Define opponent
select DIM
//------------------ROW-------------------
case 'R'
if show == 1 then
disp('Player ='), disp(P),
disp('ROW No ='), disp(IND)
end
for j=1:c
if W(IND,j) == P then M=M+1
elseif W(IND,j) == PP then MM=1, break
end
end
if MM==1 then M=0, BONUS=0
elseif M >= round(r/2) then BONUS=M
end
//------------------COL-------------------
case 'C'
if show == 1 then
disp('COLUMN No ='), disp(IND)
end
for j=1:r
if W(j,IND) == P then M=M+1
elseif W(j,IND) == PP then MM=1, break
end
end
if MM==1 then M=0, BONUS=0
elseif M >= round(r/2) then BONUS=M
end
//------------------LR DIAG-------------------
case 'L'
if show == 1 then
disp('LEFT-TO-RIGHT DIAGONAL'),
end
for j=1:c
if W(j,j) == P then M=M+1
elseif W(j,j) == PP then MM=1, break
end
end
if MM==1 then M=0, BONUS=0
elseif M >= round(r/2) then BONUS=M
end
//------------------RL DIAG-------------------
case 'D'
if show == 1 then
disp('RIGHT-TO-LEFT DIAGONAL')
end
for j=1:c
if W(j,c+1-j) == P then M=M+1
elseif W(j,c+1-j) == PP then MM=1, break
end
end
if MM==1 then M=0, BONUS=0
elseif M >= round(r/2) then BONUS=M
end
//------------------ERROR-------------------
else
error('Wrong selector in evalDir()')
break;
end
endfunction
//*********************************************
// Second Fitness function for tic-tac-toe
// tttfitn2()
//
// Idea:
// Every move of a player creates a new state w_i of a world W
// Every state w_i represents 'as it is' a potential value for a player.
// Depending on the type of player 'X' or 'O' the evaluation is different
// The value is derived from the knowledge of the 'goal states' G subset W
// In a goal state w_g.i of G one player has n pieces (n = length of board) in one direction.
// A direction is given as row or column or as diagonal.
// Thus every piece in a state w_i has a certain value with regard to the goal states:
// (i) The number of possible directions in which there is no piece of the opponent
// (ii) The number m of all pieces in one potential direction with m >= round((n/2)+1) times a bonus value
//
// Assuming Bonus = 5
// w_5:
//
// |_O_|
// |XXO|
// |X__|
//
// val_X(w_5) = 1+2+3+2xBonus + 2xBonus = 6+4xBonus = 26
//
// w_6:
//
// |_OO|
// |XXO|
// |X__|
//
// val_O(w_6) = 1+1+1+2xBonus+2xBonus = 3+4xBonus = 23
//
// Based on such an evaluation-fnction different strategied can be generated. These are not part of the
// fitnes function
//
// Counting dimensions: FLAG=[1,2,3,4,5]
// 1 : Times for Bonus
// 2 : rows
// 3 : columns
// 4 : diagonales LR
// 5 : diagonales RL
//
// Input:
// W := World as Board
// P := type of player, 'X' := Beginner, 'O' := opponent
//
// Output:
// F := fitness values
// FLAG := for control reasons
// W := world to show final state
//
// Computation:
// Looks into every direction and computes all pieces of the target player P for this direction
//
function [W,FLAG,F]=tttfit2(W,P,BON,show)
[r,c]=size(W)
FLAG = [0 0 0 0 0] // Times, Row, Col, DiaL DiaR
//*******************************
// Check all cases
// ROW
for i=1:r
[M,BONUS]=evalDir(W,'R',i,P,show)
FLAG(1,1)=FLAG(1,1)+BONUS
FLAG(1,2)=FLAG(1,2)+M
end
// COLUM
for i=1:r
[M,BONUS]=evalDir(W,'C',i,P,show)
FLAG(1,1)=FLAG(1,1)+BONUS
FLAG(1,3)=FLAG(1,3)+M
end
// DIAL
[M,BONUS]=evalDir(W,'L',0,P,show)
FLAG(1,1)=FLAG(1,1)+BONUS
FLAG(1,4)=FLAG(1,4)+M
// DIAR
[M,BONUS]=evalDir(W,'D',0,P,show)
FLAG(1,1)=FLAG(1,1)+BONUS
FLAG(1,5)=FLAG(1,5)+M
// FINAL SUM UP
F=sum(FLAG)-FLAG(1,1)+BON*FLAG(1,1)
endfunction
//****************************************************
// Match a line L with a matrix M
//
// Idea:
// Start comparison of line L with matrix M.
// Every time there is a match the results matrix TX will notify a '1'
function [TX]=mmmatch(L,M)
[r,c]=size(M)
TX=ones(r,1)
l=length(L)
for i=1:r
for j=1:l
if L(1,j)<>M(i,j) then TX(i,1)=0, break,
end //if <>
end //for j
end //for i
endfunction
//********************************************************
// Main game function tttgame() for the tic-tac-toe game
//
// Idea:
// Two players play TTT. Beginner uses the piece 'X', the opponent uses 'O'.
// Every turn one player makes a move alternating. As soon as one player has
// reached 3 pieces in one direction (rowwise, columnwise or in a diagonal) he
// has won.
//
// Input:
// W := World as a 3 x 3 grid
// show := debug
//
// Output:
// W := final state of the world
// PMatrix := Win 1 point, No-Win 0 point; left-upper corner: number of games until beginning
//
function [W,PLAYER,END]=tttgame(W,show)
P=1 //Player 1
END=0
i=1
while END == 0 & i < 10
ALLOW=0
while ALLOW == 0
[X,Y,O]=tttaction0(P), // generate a random (!) move
[W,ALLOW]=tttaction1(W,X,Y,O,show), //Check allowness (cell free, right order)
end //while ALLOW
if show == 2 then disp('Turn : '), disp(i), disp(W), end
// Check end of game
[PLAYER,END]=endgame(W,show)
if END == 0 & P==1 then P=0, else P=1 //change player
end //if
i=i+1
end //while END, i
endfunction
//********************************************************
// !!! Do not use because overwritten !!!
// Main game function tttgameA2() for the tic-tac-toe game
// Different to tttgame() is here the 2nd agent -- the opponent -- repalced by a classifier
// system instead of a pure random agent
//
// Idea:
// Two players play TTT. Beginner uses the piece 'X', the opponent uses 'O'.
// Every turn one player makes a move alternating. As soon as one player has
// reached 3 pieces in one direction (rowwise, columnwise or in a diagonal) he
// has won.
// With two random players the beginner has an advantage. In the A2 version the random
// opponent is replaced by a learning classifier system. The questioin is, whether the
// LCS can beat the random agent.
//
// Input:
// W := World as a 3 x 3 grid
// AGENT := Name of Agent as opponent
// show := debug
//
// Output:
// W := final state of the world
//
function [W,PLAYER,END,CLASSIF]=tttgameA2_old(W,AGENT, CLASSIF, show)
P=1 //Player 1
END=0
n=9,l=26 //n=9 is deliberately, can be changed; l=28 is minimum
AGENT(1) = CLASSIF
//Start a general loop for the game alternating between the beginner 'X' playing completely at random
// and as opponent an LCS using 'O'.
i=1
while END == 0 & i < 10
if show == 2 then disp('TURN = '), disp(i), disp('PLAYER = '), disp(P), end
ALLOW=0
if P == 1 then O='X'
while ALLOW == 0
[X,Y,O]=tttaction0(P), // generate a random (!) move
[W,ALLOW]=tttaction1b(W,X,Y,O,show), //Check allowness (cell free, right order)
end //if P=1
elseif P == 2 then O='O'
// Get input of state
[INP]=ainp2(W)
l=length(INP)
if show == 2 then disp('INP = '), disp(INP), end
//Check match with given classifiers
[TX]=mmmatch(INP,AGENT(1)) //AGENT(1) uses classifier set CLASSIF
if sum(TX) == 0 then //no match
while ALLOW == 0
[X,Y,O]=tttaction0(P), // generate a random (!) move to find a free cell
[F,FLAG,ALLOW,W]=tttfitn(W,X,Y,O,show) //Check allowness, insert object, and evaluate fitness
end
if show == 2 then disp('X ='), disp(X), disp('Y ='), disp(Y), end
if show == 2 then disp('FLAG PLAYER 2 ='), disp(FLAG), disp('FITNESS ='), disp(F), end
[G]=classifNew(INP,X,Y,F,show) // Now new classifier
CLASSIF=[CLASSIF; G(1,:)] //Extending the set CLASSIF by G
else //There is a match
if show == 2 then disp('TX = '), disp(TX), end
// if show == 2 then disp('CLASSIF = '), disp(CLASSIF), end
// if show == 2 then disp('Select matching classifiers'), end
//find classifier with highest fitness
CSel=[]
FMax=0
[n,c2]=size(TX)
//Find MAX Fitness
for k=1:n
if TX(k,1) == 1 & CLASSIF(k,25)>FMax then FMax = CLASSIF(k,25),
end
end
//Select candidates
j=1
for k=1:n
if TX(k,1) == 1 & CLASSIF(k,25) == FMax then CSel(j,1)=k, j=j+1
end
end
if show == 2 then disp('Candidates after matching'),
disp(CSel),
end
[n2,c3]=size(CSel)
cc=round(rand()*n2)
if cc == 0 then cc = 1,end
ccc=CSel(cc,1)
G=CLASSIF(ccc,:)
if show == 2 then disp('Selected Candidate from Candidates after matching'),
disp('No = '), disp(ccc), disp(G),
end
//Extract coordinates for move
X=vec22dec(G(1,:),21,22), Y=vec22dec(G(1,:),23,24)
[F,FLAG,ALLOW,W]=tttfitn(W,X,Y,O,show) //Check allowness, insert object, and evaluate fitness
if ALLOW == 0 then
while ALLOW == 0
[X,Y,O]=tttaction0(P), // generate a random (!) move to find a free cell
[F,FLAG,ALLOW,W]=tttfitn(W,X,Y,O,show) //Check allowness, insert object, and evaluate fitness
end //while
[G]=classifNew(INP,X,Y,F,show) // Now new classifier
CLASSIF=[CLASSIF; G(1,:)] //Extending classif by G as vector
if show == 2 then
disp('Matched Classifier with new move'), disp('X ='), disp(X), disp('Y ='), disp(Y),
end
if show == 2 then disp('FLAG PLAYER 2 ='), disp(FLAG), disp('FITNESS ='), disp(F), end
else //ALLOW == 1
CLASSIF(ccc,25)=F
if show == 2 then
disp('Matched Classifier with old, new fitness'), disp('X ='), disp(X), disp('Y ='), disp(Y),
end
if show == 2 then disp('FLAG PLAYER 2 ='), disp(FLAG), disp('FITNESS ='), disp(F), end
end
end //if sum
// Computing the fitness of CLASSIF
end //P=1 oder P=2
if show == 2 then disp('BOARD : '), disp(W), end
// Check end of game
[PLAYER,END]=endgame(W,show)
if show == 2 then disp('END : '), disp(END), end
if (END == 0) then
if (P == 1) then P=2,
else P=1 //change player
end //if P==1
end //if END
i=i+1
end //while END, i
endfunction
//********************************************************
// Main game function tttgameA2() for the tic-tac-toe game
// Different to tttgame() is here the 2nd agent -- the opponent -- replaced by a classifier
// system instead of a pure random agent
//
// Idea:
// Two players play TTT. Beginner uses the piece 'X', the opponent uses 'O'.
// Every turn one player makes a move alternating. As soon as one player has
// reached 3 pieces in one direction (rowwise, columnwise or in a diagonal) he
// has won.
// With two random players the beginner has an advantage. In the A2 version the random
// opponent is replaced by a learning classifier system. The questioin is, whether the
// LCS can beat the random agent.
//
// Input:
// W := World as a 3 x 3 grid
// AGENT := Name of agent as opponent
// show := debug
//
// Output:
// W := final state of the world
// PLAYER := Who has won {'X', 'O'}
// END := Ended '1' or not '0'
// CLASSIF := Final set of classifiers
//
function [W,PLAYER,END,CLASSIF]=tttgameA2(W,AGENT, CLASSIF, show)
P=1 //Player 1
END=0
n=9,l=26 //n=9 is deliberately, can be changed; l=28 is minimum
AGENT(1) = CLASSIF
BON=5 //Bonus for fitness function
//Start a general loop for the game alternating between the beginner 'X' playing completely at random
// and as opponent an LCS using 'O'.
i=1
P=1
while END == 0 & i < 10
if show == 2 then disp('TURN = '), disp(i), disp('PLAYER = '), disp(P),
end
//*****************************************************
//TURN with P1
//*****************************************************
if P == 1 then O='X'
[CLst]=freeCells(W,show) //List of free cells
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
W(Y,X)='X' // New move for 'X'
//*****************************************************
//TURN with P2
//*****************************************************
elseif P == 2 then O='O'
//********************************
// Get input of state
[INP]=ainp2(W)
l=length(INP)
if show == 2 then disp('INP = '), disp(INP),
end
//********************************
//Check match with given classifiers
[TX]=mmmatch(INP,AGENT(1)) //AGENT(1) uses classifier set CLASSIF
if sum(TX) == 0 then
//********************************
// No match
// Generate new move with new classifier
if show == 2 then disp('X ='), disp(X), disp('Y ='), disp(Y), end
[CLst]=freeCells(W,show) //List of free cells
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
W(Y,X)='O'
[W,FLAG,F]=tttfit2(W,'O',BON,show)
[G]=classifNew(INP,X,Y,F,show) // Now new classifier
CLASSIF=[CLASSIF; G(1,:)] //Extending the set CLASSIF by G
else
//****************************************
//There is a match
if show == 2 then disp('TX = '), disp(TX),
end
// if show == 2 then disp('CLASSIF = '), disp(CLASSIF), end
// if show == 2 then disp('Select matching classifiers'), end
//find classifier with highest fitness
CSel=[]
FMax=0
[n,c2]=size(TX)
//Find MAX Fitness
for k=1:n
if TX(k,1) == 1 & CLASSIF(k,25)>FMax then FMax = CLASSIF(k,25),
end
end
//Select candidates
j=1
for k=1:n
if TX(k,1) == 1 & CLASSIF(k,25) == FMax then CSel(j,1)=k, j=j+1
end
end
if show == 2 then disp('Candidates after matching'),
disp(CSel),
end
[n2,c3]=size(CSel)
// Find a candidate whose move matches free cells
//List of free cells
[CLst]=freeCells(W,show)
[r3,c4]=size(CLst)
r=1
while (r <= n2)
//Search for every candidate from CSel
G=CLASSIF(CSel(r,1),:)
if show == 2 then disp('Selected Candidate from Candidates after matching'),
disp('No = '), disp(CSel(r,1)), disp(G),
end
//Extract coordinates for move
X=vec22dec(G(1,:),21,22),
Y=vec22dec(G(1,:),23,24)
ALLOW=0
k=1
while(ALLOW==0 & k <= r3)
//Search all free cells for one classifier
if CLst(k,1)==Y & CLst(k,2)==X then
//If a cell matches insert Object according classifier
W(Y,X)='O',
[W,FLAG,F]=tttfit2(W,'O',BON,show)
// Update classifier with fitness
CLASSIF(CSel(r,1),25)=F,
ALLOW=1
if show == 2 then
disp('Matched Classifier with old, new fitness'), disp('X ='), disp(X), disp('Y ='), disp(Y),
end
break
end //if there is a match
k=k+1
end //while
r=r+1
end //while r
if ALLOW==0 then
//No free cell for no selected classifier could be found
// Create new classifier
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
W(Y,X)='O'
[W,FLAG,F]=tttfit2(W,'O',BON,show)
[G]=classifNew(INP,X,Y,F,show) // New classifier
CLASSIF=[CLASSIF; G(1,:)] //Extending classif by G as vector
if show == 2 then
disp('New Classifier because matched had wrong move'), disp('X ='), disp(X), disp('Y ='), disp(Y),
end
if show == 2 then disp('FLAG PLAYER 2 ='), disp('FITNESS ='), disp(F),
end
end // if no match with old classifiers
end //if sum
end //P=1 oder P=2
if show == 2 then disp('BOARD : '), disp(W), end
// Check end of game
[PLAYER,END]=endgame(W,show)
if show == 2 then disp('END : '), disp(END), end
if (END == 0) then
if (P == 1) then P=2,
else P=1 //change player
end //if P==1
end //if END
i=i+1
end //while END, i
endfunction
//********************************************************
// Main game function tttgameA3() for the tic-tac-toe game
// Different to tttgameA2() is here the inclusion of simple genetic operators
//
// Input:
// W := World as a 3 x 3 grid
// AGENT := Name of agent as opponent
// show := debug
//
// Output:
// W := final state of the world
// PLAYER := Who has won {'X', 'O'}
// END := Ended '1' or not '0'
// CLASSIF := Final set of classifiers. It is assumed that the set CLASSIF has the miimal size of
// c = l + p
// with 'l=24' length of strings and 'p=7' as parameter offset
//
function [W,PLAYER,END,CLASSIF]=tttgameA3(W,AGENT, CLASSIF, l,p,show)
P=1 //Player 1
END=0
[rw,cw]=size(W), n=rw*cw
[rc,cc]=size(CLASSIF)
AGENT(1) = CLASSIF
BON=5 //Bonus for fitness function
FITNESS_ALL = 0
//Start a general loop for the game alternating between the beginner 'X' playing completely at random
// and as opponent an LCS using 'O'.
i=1
P=1
while END == 0 & i < 10
if show == 2 then disp('TURN = '), disp(i), disp('PLAYER = '), disp(P),
end
//*****************************************************
//TURN with P1
//*****************************************************
if P == 1 then O='X'
[CLst]=freeCells(W,show) //List of free cells
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
W(Y,X)='X' // New move for 'X'
//*****************************************************
//TURN with P2
//*****************************************************
elseif P == 2 then O='O'
//********************************
// Get input of state
[INP]=ainp2(W)
l=length(INP)
if show == 2 then disp('INP = '), disp(INP),
end
//********************************
//Check match with given classifiers
[TX]=mmmatch(INP,AGENT(1)) //AGENT(1) uses classifier set CLASSIF
if sum(TX) == 0 then
//********************************
// No match
// Generate new move with new classifier
if show == 2 then disp('X ='), disp(X), disp('Y ='), disp(Y), end
[CLst]=freeCells(W,show) //List of free cells
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
W(Y,X)='O'
[W,FLAG,F]=tttfit2(W,'O',BON,show)
//disp('Before classifNew')
[rr,cc]=size(CLASSIF)
[G]=classifNew2(INP,X,Y,F,rr,cc,show) // Now new classifier
//disp('After classifNew'),disp('G ='), disp(G)
CLASSIF=[CLASSIF; G(1,:)] //Extending the set CLASSIF by G
else
//****************************************
//There is a match
if show == 2 then disp('TX = '), disp(TX),
end
//find classifier with highest fitness
CSel=[]
FMax=0
[n,c2]=size(TX)
//Find MAX Fitness
for k=1:n
if TX(k,1) == 1 & CLASSIF(k,25)>FMax then FMax = CLASSIF(k,25),
end
end
//Select candidates
j=1
for k=1:n
if TX(k,1) == 1 & CLASSIF(k,25) == FMax then CSel(j,1)=k, j=j+1
end
end
if show == 2 then disp('Candidates after matching'),
disp(CSel),
end
[n2,c3]=size(CSel)
// Find a candidate whose move matches free cells
//List of free cells
[CLst]=freeCells(W,show)
[r3,c4]=size(CLst)
r=1
while (r <= n2)
//Search for every candidate from CSel
G=CLASSIF(CSel(r,1),:)
if show == 2 then disp('Selected Candidate from Candidates after matching'),
disp('No = '), disp(CSel(r,1)), disp(G),
end
//Extract coordinates for move
//1-18 := 3x3 board
//19-20 := X
// 21-22 := Y
// 23-24 := O
// 25 := F
X=vec22dec(G(1,:),19,20),
Y=vec22dec(G(1,:),21,22)
ALLOW=0
k=1
while(ALLOW==0 & k <= r3)
//Search all free cells for one classifier
if CLst(k,1)==Y & CLst(k,2)==X then
//If a cell matches insert Object according classifier
W(Y,X)='O',
[W,FLAG,F]=tttfit2(W,'O',BON,show)
// Update classifier with fitness
CLASSIF(CSel(r,1),25)=F,
ALLOW=1
if show == 2 then
disp('Matched Classifier with old, new fitness'),disp(CLASSIF(CSel(r,1),:))
end
break
end //if there is a match
k=k+1
end //while
r=r+1
end //while r
if ALLOW==0 then
//No free cell for no selected classifier could be found
// Create new classifier
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
W(Y,X)='O'
[W,FLAG,F]=tttfit2(W,'O',BON,show)
[rr,cc]=size(CLASSIF)
[G]=classifNew2(INP,X,Y,F,rr,cc,show)// New classifier
CLASSIF=[CLASSIF; G(1,:)] //Extending classif by G as vector
if show == 2 then
disp('New Classifier because matched had wrong move'), disp(G(1,:))
end
if show == 2 then disp('FLAG PLAYER 2 ='), disp('FITNESS ='), disp(F),
end
end // if no match with old classifiers
end //if sum
//***********************************************
// Apply crossover
//****************************************************
l=23 //fitness assumes F at l+2, but with CLASSIF F is at l+1!
[FITNESS_ALL]=fitness(CLASSIF,l)
if FITNESS_ALL == 0 then FITNESS_ALL=FITNESS_ALL+0.0001,end
l=23 //fitness assumes F at l+2, but with CLASSIF F is at l+1!
[MFITNESS]=maxfitness(CLASSIF,l)
l=23 //fitness assumes F at l+2, but with CLASSIF F is at l+1!
[CLASSIF,AFITNESS]=rfitness(CLASSIF,l,FITNESS_ALL)
if show == 4 then
disp('CLASSIF after rfitness'), disp(CLASSIF)
end
// if show == 1 then disp(CLASSIF), end
[CLASSIF]=newMember(CLASSIF,l,n)
if show == 1 then disp(CLASSIF), end
[CLASSIF]=newPop2(CLASSIF,l,p,n)
end //P=1 oder P=2
if show == 2 then disp('BOARD : '), disp(W), end
// Check end of game
[PLAYER,END]=endgame(W,show)
if show == 2 then disp('END : '), disp(END), end
if (END == 0) then
if (P == 1) then P=2,
else P=1 //change player
end //if P==1
end //if END
i=i+1
end //while END, i
endfunction
//********************************************************
// Main game function tttgameA3X() for the tic-tac-toe game
// Different to tttgameA3() is here that the LCS system is the beginner
//
// Input:
// W := World as a 3 x 3 grid
// AGENT := Name of agent as opponent
// show := debug
//
// Output:
// W := final state of the world
// PLAYER := Who has won {'X', 'O'}
// END := Ended '1' or not '0'
// CLASSIF := Final set of classifiers. It is assumed that the set CLASSIF has the miimal size of
// c = l + p
// with 'l=24' length of strings and 'p=7' as parameter offset
//
function [W,PLAYER,END,CLASSIF]=tttgameA3X(W,AGENT, CLASSIF, l,p,show)
P=1 //Player 1
END=0
[rw,cw]=size(W), n=rw*cw
[rc,cc]=size(CLASSIF)
AGENT(1) = CLASSIF
BON=5 //Bonus for fitness function
FITNESS_ALL = 0
//Start a general loop for the game alternating between the beginner 'X' playing completely at random
// and as opponent an LCS using 'O'.
i=1
P=1
while END == 0 & i < 10
if show == 2 then disp('TURN = '), disp(i), disp('PLAYER = '), disp(P),
end
//*****************************************************
//TURN with P1 as LCS
//*****************************************************
if P == 1 then O='X'
//********************************
// Get input of state
[INP]=ainp2(W)
l=length(INP)
if show == 2 then disp('INP = '), disp(INP),
end
//********************************
//Check match with given classifiers
[TX]=mmmatch(INP,AGENT(1)) //AGENT(1) uses classifier set CLASSIF
if sum(TX) == 0 then
//********************************
// No match
// Generate new move with new classifier
[CLst]=freeCells(W,show) //List of free cells
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
if show == 2 then disp('X ='), disp(X), disp('Y ='), disp(Y), end
W(Y,X)='X'
[W,FLAG,F]=tttfit2(W,'X',BON,show)
//disp('Before classifNew')
[rr,cc]=size(CLASSIF)
[G]=classifNew2(INP,X,Y,F,rr,cc,show) // Now new classifier
//disp('After classifNew'),disp('G ='), disp(G)
CLASSIF=[CLASSIF; G(1,:)] //Extending the set CLASSIF by G
else
//****************************************
//There is a match
if show == 2 then disp('TX = '), disp(TX),
end
//find classifier with highest fitness
CSel=[]
FMax=0
[n,c2]=size(TX)
//Find MAX Fitness
for k=1:n
if TX(k,1) == 1 & CLASSIF(k,25)>FMax then FMax = CLASSIF(k,25),
end
end
//Select candidates
j=1
for k=1:n
if TX(k,1) == 1 & CLASSIF(k,25) == FMax then CSel(j,1)=k, j=j+1
end
end
if show == 2 then disp('Candidates after matching'),
disp(CSel),
end
[n2,c3]=size(CSel)
// Find a candidate whose move matches free cells
//List of free cells
[CLst]=freeCells(W,show)
[r3,c4]=size(CLst)
r=1
while (r <= n2)
//Search for every candidate from CSel
G=CLASSIF(CSel(r,1),:)
if show == 2 then disp('Selected Candidate from Candidates after matching'),
disp('No = '), disp(CSel(r,1)), disp(G),
end
//Extract coordinates for move
//1-18 := 3x3 board
//19-20 := X
// 21-22 := Y
// 23-24 := O
// 25 := F
X=vec22dec(G(1,:),19,20),
Y=vec22dec(G(1,:),21,22)
ALLOW=0
k=1
while(ALLOW==0 & k <= r3)
//Search all free cells for one classifier
if CLst(k,1)==Y & CLst(k,2)==X then
//If a cell matches insert Object according classifier
W(Y,X)='X',
[W,FLAG,F]=tttfit2(W,'X',BON,show)
// Update classifier with fitness
CLASSIF(CSel(r,1),25)=F,
ALLOW=1
if show == 2 then
disp('Matched Classifier with old, new fitness'),disp(CLASSIF(CSel(r,1),:))
end
break
end //if there is a match
k=k+1
end //while
r=r+1
end //while r
if ALLOW==0 then
//No free cell for no selected classifier could be found
// Create new classifier
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
W(Y,X)='X'
[W,FLAG,F]=tttfit2(W,'X',BON,show)
[rr,cc]=size(CLASSIF)
[G]=classifNew2(INP,X,Y,F,rr,cc,show)// New classifier
CLASSIF=[CLASSIF; G(1,:)] //Extending classif by G as vector
if show == 2 then
disp('New Classifier because matched had wrong move'), disp(G(1,:))
end
if show == 2 then disp('FLAG PLAYER 2 ='), disp('FITNESS ='), disp(F),
end
end // if no match with old classifiers
end //if sum
//***********************************************
// Apply crossover
//****************************************************
l=23 //fitness assumes F at l+2, but with CLASSIF F is at l+1!
[FITNESS_ALL]=fitness(CLASSIF,l)
if FITNESS_ALL == 0 then FITNESS_ALL=FITNESS_ALL+0.0001,end
l=23 //fitness assumes F at l+2, but with CLASSIF F is at l+1!
[MFITNESS]=maxfitness(CLASSIF,l)
l=23 //fitness assumes F at l+2, but with CLASSIF F is at l+1!
[CLASSIF,AFITNESS]=rfitness(CLASSIF,l,FITNESS_ALL)
if show == 4 then
disp('CLASSIF after rfitness'), disp(CLASSIF)
end
// if show == 1 then disp(CLASSIF), end
[CLASSIF]=newMember(CLASSIF,l,n)
if show == 1 then disp(CLASSIF), end
[CLASSIF]=newPop2(CLASSIF,l,p,n)
//*****************************************************
//TURN with P2 as random opponent
//*****************************************************
elseif P == 2 then O='O'
[CLst]=freeCells(W,show) //List of free cells
N=length(CLst)/2,
[K]=freeCellIndex(N) //Index into this list
Y=CLst(K,1), X=CLst(K,2)
W(Y,X)='O' // New move for 'O'
end //P=1 oder P=2
if show == 2 then disp('BOARD : '), disp(W), end
// Check end of game
[PLAYER,END]=endgame(W,show)
if show == 2 then disp('END : '), disp(END), end
if (END == 0) then
if (P == 1) then P=2,
else P=1 //change player
end //if P==1
end //if END
i=i+1
end //while END, i
endfunction
//********************************************************
// Main tournament function ttttournament() for the tic-tac-toe game
//
// Idea:
// The tournament function can repeatedly call a tttgame() function where two players can have alternating
// roles either as beginner or as opponent to a beginner. Furthermore will the results be kept in a
// game matrix with '1' for e win and '0' for a non-win.
//
// Input:
// W := World as a 3 x 3 grid
// p := Number of players which shall play
// N := number of games to be played against each other (usuall x2 because of two roles)
// show := debug
//
// Output:
// PMatrix := Win 1 point, No-Win 0 point; left-upper corner: number of games until beginning
//
function [PMatrix]=ttttournament(W,p,N,show)
[PList]=plistgen(p)
[PMatrix]=pmatrixgen(PList)
if show == 3 then disp(PMatrix),end
for i=1:N
ROLE=0 //Player P1 is beginner
WI=W //Use empty world for each game
//if show == 3 then disp('Before tttgame() '), disp(i), disp(W),end
[WE,PLAYER,END]=tttgame(WI,show),
if show == 3 then disp('Round = '), disp(i), disp(WE),end
// Insert results in game table
if PLAYER == 'X' then PMatrix(2,2)=PMatrix(2,2)+1,
elseif PLAYER == 'O' then PMatrix(2,3)=PMatrix(2,3)+1,
end
PMatrix(1,1)=PMatrix(1,1)+1
end //for i
endfunction
//********************************************************
// Main tournament function ttttournament2() for the tic-tac-toe game
//
// Idea:
// The tournament function can repeatedly call a tttgame() function where two players can have alternating
// roles either as beginner or as opponent to a beginner. Furthermore will the results be kept in a
// game matrix with '1' for e win and '0' for a non-win.
//
// Input:
// W := World as a 3 x 3 grid
// p := Number of players which shall play
// N := number of games to be played against each other (usuall x2 because of two roles)
// show := debug
//
// Output:
// PMatrix := Win 1 point, No-Win 0 point; left-upper corner: number of games until beginning
//
function [PMatrix, PX,PY]=ttttournament2(W,p,N,show)
[PList]=plistgen(p)
[PMatrix]=pmatrixgen(PList)
if show == 3 then disp(PMatrix),end
for i=1:N
ROLE=0 //Player P1 is beginner
WI=W //Use empty world for each game
//if show == 3 then disp('Before tttgame() '), disp(i), disp(W),end
[WE,PLAYER,END]=tttgame(WI,show),
if show == 3 then disp('Round = '), disp(i), disp(WE),end
// Insert results in game table
if PLAYER == 'X' then PMatrix(2,2)=PMatrix(2,2)+1,
elseif PLAYER == 'O' then PMatrix(2,3)=PMatrix(2,3)+1,
end
PMatrix(1,1)=PMatrix(1,1)+1
end //for i
PlayerX = sum(PMatrix(:,2))-1, PX = PlayerX/(PMatrix(1,1)/100)
PlayerY = sum(PMatrix(:,3))-2, PY = PlayerY/(PMatrix(1,1)/100)
disp('RESULT ='), disp('Player X = '), disp(PX), disp('Player Y = '), disp(PY)
endfunction
//********************************************************
// Main tournament function ttttournamentA2() for the tic-tac-toe game
// assuming one opponent player with learning classifiers
//
// Idea:
// The tournament function can repeatedly call a tttgameA2() function where the opponent is the one which uses
// classifiers. Furthermore will the results be kept in a
// game matrix with '1' for e win and '0' for a non-win.
//
// Input:
// W := World as a 3 x 3 grid
// AGENT := which type of agent shall be used
// N := number of games to be played against each other
// CLASSIF := Set of classifiers of opponent which will beinherited from game to game
// show := debug
//
// Output:
// PMatrix := Win 1 point, No-Win 0 point; left-upper corner: number of games until beginning
// CLASSIF := Set of classifiers of opponent which will beinherited from game to game
//
function [PMatrix, CLASSIF,PX, PY]=ttttournamentA2(W,AGENT,CLASSIF,N,show)
[PMatrix]=pmatrixgenA2(N) //Table for 2 players and N-many games
if show == 3 then disp(PMatrix),end
for i=1:N
WI=W //Use empty world for each game
//if show == 3 then disp('Before tttgame() '), disp(i), disp(W),end
[WE,PLAYER,END,CLASSIF]=tttgameA2(WI,AGENT, CLASSIF, show)
if show == 3 then disp('Round = '), disp(i), disp(WE),end
// Insert results in game table
if PLAYER == 'X' then PMatrix(i+1,2)=PMatrix(i+1,2)+1,
elseif PLAYER == 'O' then PMatrix(i+1,3)=PMatrix(i+1,3)+1,
end
PMatrix(1,1)=PMatrix(1,1)+1
end //for i
PlayerX = sum(PMatrix(:,2))-1, PX = PlayerX/(PMatrix(1,1)/100)
PlayerY = sum(PMatrix(:,3))-2, PY = PlayerY/(PMatrix(1,1)/100)
disp('RESULT ='), disp('Player X = '), disp(PX), disp('Player Y = '), disp(PY)
endfunction
//********************************************************
// Main tournament function ttttournamentA3() for the tic-tac-toe game
// assuming one opponent player with learning classifiers
//
//Input additionally:
// l:= length of information part (24)
// p := offset (7)
function [PMatrix, CLASSIF,PX, PY]=ttttournamentA3(W,AGENT,CLASSIF,N,l,p,show)
[PMatrix]=pmatrixgenA2(N) //Table for 2 players and N-many games
if show == 3 then disp(PMatrix),end
for i=1:N
WI=W //Use empty world for each game
//if show == 3 then disp('Before tttgame() '), disp(i), disp(W),end
[WE,PLAYER,END,CLASSIF]=tttgameA3(WI,AGENT, CLASSIF, l,p,show)
if show == 5 then disp('Round = '), disp(i), disp(WE),end
// Insert results in game table
if PLAYER == 'X' then PMatrix(i+1,2)=PMatrix(i+1,2)+1,
elseif PLAYER == 'O' then PMatrix(i+1,3)=PMatrix(i+1,3)+1,
end
PMatrix(1,1)=PMatrix(1,1)+1
end //for i
PlayerX = sum(PMatrix(:,2))-1, PX = PlayerX/(PMatrix(1,1)/100)
PlayerY = sum(PMatrix(:,3))-2, PY = PlayerY/(PMatrix(1,1)/100)
disp('RESULT ='), disp('Player X = '), disp(PX), disp('Player Y = '), disp(PY)
endfunction
//********************************************************
// Main tournament function ttttournamentA3X() for the tic-tac-toe game
// assuming one beginning player with learning classifiers
//
//Input additionally:
// l:= length of information part (24)
// p := offset (7)
function [PMatrix, CLASSIF,PX, PY]=ttttournamentA3X(W,AGENT,CLASSIF,N,l,p,show)
[PMatrix]=pmatrixgenA2(N) //Table for 2 players and N-many games
if show == 3 then disp(PMatrix),end
for i=1:N
WI=W //Use empty world for each game
//if show == 3 then disp('Before tttgame() '), disp(i), disp(W),end
[WE,PLAYER,END,CLASSIF]=tttgameA3X(WI,AGENT, CLASSIF, l,p,show)
if show == 5 then disp('Round = '), disp(i), disp(WE),end
// Insert results in game table
if PLAYER == 'X' then PMatrix(i+1,2)=PMatrix(i+1,2)+1,
elseif PLAYER == 'O' then PMatrix(i+1,3)=PMatrix(i+1,3)+1,
end
PMatrix(1,1)=PMatrix(1,1)+1
end //for i
PlayerX = sum(PMatrix(:,2))-1, PX = PlayerX/(PMatrix(1,1)/100)
PlayerY = sum(PMatrix(:,3))-2, PY = PlayerY/(PMatrix(1,1)/100)
disp('RESULT ='), disp('Player X = '), disp(PX), disp('Player Y = '), disp(PY)
endfunction
//********************************************************
// Tournament history tournamenthistory()
// With two random agents as benchmark
//
// The set CLASSIF is not used
//
//Input additionally:
// l:= length of information part (24)
// p := offset (7)
function [PMX]=ttttournamenthistory(W,N,M,show)
p=2
PMX=[]
for i= 1:M
[PMatrix, PX,PY]=ttttournament2(W,p,N,show)
PMX(i,1)=i
PMX(i,2)=PX
PMX(i,3)=PY
disp('--------------------------------'),disp('Tournament No. ='), disp(i), disp('--------------------------------')
end //end i
//Show final table
disp(PMX)
MEAN_X=mean(PMX(:,2))
STD_X=st_deviation(PMX(:,2))
MEAN_O=mean(PMX(:,3))
STD_O=st_deviation(PMX(:,3))
disp('MEAN_X='), disp(MEAN_X),disp('STD_X='), disp(STD_X),
disp('MEAN_O='), disp(MEAN_O),disp('STD_O='), disp(STD_O),
//Show Plot
X=[1:1:M]';
clf()
xdel
Y1=PMX(:,2)
Y2=PMX(:,3)
plot2d(X,[Y1 Y2])
endfunction
//********************************************************
// Tournament history tournamentA2history()
//
// Idea:
// Collects all results of different tournaments to show a graph
//
// Input:
// W := World as a 3 x 3 grid
// AGENT := which type of agent shall be used
// CLASSIF := Set of classifiers of opponent which will beinherited from game to game
// N := number of games to be played against each other
// M := number of tournaments to be played against each other
// show := debug
//
// Output:
// PMX := List of tournament results
// CLASSIF := Set of classifiers of opponent which will beinherited from game to game
//
function [PMX,CLASSIF]=ttttournamentA2history(W,AGENT,CLASSIF,N,M,show)
PMX=[]
for i= 1:M
[PMatrix, CLASSIF,PX, PY]=ttttournamentA2(W,AGENT,CLASSIF,N,show)
PMX(i,1)=i
PMX(i,2)=PX
PMX(i,3)=PY
disp('--------------------------------'),disp('Tournament No. ='), disp(i), disp('--------------------------------')
fd=mopen('CLASSIF'+string(evstr(i)),'w')
fprintfMat('CLASSIF'+string(evstr(i)),CLASSIF,'%1f');
mclose(fd)
end
X=[1:1:M]';
clf()
xdel
Y1=PMX(:,2)
Y2=PMX(:,3)
plot2d(X,[Y1 Y2])
endfunction
//********************************************************
// Tournament history tournamentA3history()
//
//Input additionally:
// l:= length of information part (24)
// p := offset (7)
function [PMX,CLASSIF]=ttttournamentA3history(W,AGENT,CLASSIF,N,M,l,p,show)
PMX=[]
for i= 1:M
[PMatrix, CLASSIF,PX, PY]=ttttournamentA3(W,AGENT,CLASSIF,N,l,p,show)
PMX(i,1)=i
PMX(i,2)=PX
PMX(i,3)=PY
disp('--------------------------------'),disp('Tournament No. ='), disp(i), disp('--------------------------------')
fd=mopen('CLASSIF'+string(evstr(i)),'w')
fprintfMat('CLASSIF'+string(evstr(i)),CLASSIF,'%1f');
mclose(fd)
end
//Show final table
disp(PMX)
MEAN_X=mean(PMX(:,2))
STD_X=st_deviation(PMX(:,2))
MEAN_O=mean(PMX(:,3))
STD_O=st_deviation(PMX(:,3))
disp('MEAN_X='), disp(MEAN_X),disp('STD_X='), disp(STD_X),
disp('MEAN_O='), disp(MEAN_O),disp('STD_O='), disp(STD_O),
//Show Plot
X=[1:1:M]';
clf()
xdel
Y1=PMX(:,2)
Y2=PMX(:,3)
plot2d(X,[Y1 Y2])
endfunction
//********************************************************
// Tournament history tournamentA3Xhistory()
//
//Input additionally:
// l:= length of information part (24)
// p := offset (7)
function [PMX,CLASSIF]=ttttournamentA3Xhistory(W,AGENT,CLASSIF,N,M,l,p,show)
PMX=[]
for i= 1:M
[PMatrix, CLASSIF,PX, PY]=ttttournamentA3X(W,AGENT,CLASSIF,N,l,p,show)
PMX(i,1)=i
PMX(i,2)=PX
PMX(i,3)=PY
disp('--------------------------------'),disp('Tournament No. ='), disp(i), disp('--------------------------------')
fd=mopen('CLASSIF'+string(evstr(i)),'w')
fprintfMat('CLASSIF'+string(evstr(i)),CLASSIF,'%1f');
mclose(fd)
end
//Show final table
disp(PMX)
MEAN_X=mean(PMX(:,2))
STD_X=st_deviation(PMX(:,2))
MEAN_O=mean(PMX(:,3))
STD_O=st_deviation(PMX(:,3))
disp('MEAN_X='), disp(MEAN_X),disp('STD_X='), disp(STD_X),
disp('MEAN_O='), disp(MEAN_O),disp('STD_O='), disp(STD_O),
//Show Plot
X=[1:1:M]';
clf()
xdel
Y1=PMX(:,2)
Y2=PMX(:,3)
plot2d(X,[Y1 Y2])
endfunction
//*******************************************************************************************
// All data are organized in a dynamical table. Left hand the actual genes, in the middle
// supporting parameters and to the right intermediate modifications of the genes to the left.
//
// POP FORMAT
// l := length of strings
// p := number of cells between string <1...l> and <l+p+1, ..., l+p+l>
// Pos 1-l := String
// Pos l+1 := Decimal Value of binary string
// Pos l+2 := Fitness for l+1 (and l+p in special cases)
// Pos l+3 := Percentage of overall fitness
// Pos l+4 := Expected count according to fitness
// Pos l+5 := Realized count
// Pos l+6 := 2nd Decimal value of a compund fitness
// Pos l+7 := crossover flag
// p := 7
// Variable for overall Fitness
FITNESS_ALL = 0
// Variable for average Fitness
AFITNESS = 0
//***************************************************
//Function to generate automatically a population with random values
// Input:
// l := length of strings
// n := size of population
// Output:
// A population according to the above defined format
//
function[POPX]=popgen(n,l)
//Generate a matrix with only '0's
POPX = zeros(n,l)
MaxCells = n*l
// Distribute randomly '1's
for i=1:n
for j=1:l
if( rand() < 0.5 ) then POPX(i,j) = 0, else POPX(i,j) = 1, end
end
end
endfunction
//***************************************************
//Function to test the randomness of a bit-string
// (see: A.L.Rukhin 2011, Statistical Testing of Randomness)
//
// Input:
// POP := Set of binary strings of length l
//
// Output:
// PX := Set of Probabilities of binary strings with
// binary string as (S_n + n)/2 and S_n = X_1 + ... + X_n
// X_k = 2e_k - 1 (k in [1,n] and e in {0,1})
function[STD,M,PX]=bitness(POP,l)
[r,c] = size(POP)
PX = zeros(r,3)
M=0
for i=1:r, PX(i,1)=i,
for j=1:l,PX(i,2)=PX(i,2)+(2*POP(i,j)-1),end,
PX(i,2)=(PX(i,2)+l)/2,
PX(i,3)=PX(i,2)/l, M=M+PX(i,3),
end
M=M/r
STD=st_deviation(PX(:,3))
endfunction
//***************************************************
//Function to generate random numbers between [1,up]
//
// n := number of choices
function[Xs]=randInt(n, up)
Xs = []
for i=1:n
x=0
while(x==0)
x = round(up*rand())
end
Xs(i) = x
end
endfunction
//***************************************************
//Function to compute descriptive parameters of a population
// Input:
// l := length of strings
// n := size of population
// Output:
// Pc := Percentage of possible space (PSpace)
// Pb := Probability of gitting a certain individual of PSpace
function[Pc, Pb]=popDescr(n,l)
// Cardinality of PSpace
PSPC = 2^l
// Percentage Pc
Pc = n/(PSPC/100)
// Probability Pb
Pb = n/2^l
endfunction
//***************************************************
//Function to compute the frequencies of the elements of a population
//
// Input:
// l := length of strings
// n := size of population
// N := number of events
// show := if '1' then display the POPX-matrix
//
// Output:
// FX := Vector of freuencies ordered along the decimal values of a string (1st column)
// FXDif := Vector of Differences compared to theoretical expectation in % (2nd column)
// MEAN := The mean value of the differences
// STD := The standard deviation of the differences
//
// Idea: Generate a sequence of populations, count the occurences, and check the degree of agreement between
// empirical values and theoretica lexpectations
function[DIST2,STD, MEAN, FREQ,STD1, MEAN1, FREQ1,FX, POPX]=frequCheck(l,n,N,show)
// Install the counters
r= (2^l)
c= 3
FX = zeros(r,c)
// Generate an internal index for display
for j=1:r
FX(j,1)=j-1
end
// Generate the populations
for i=1:N
[POPX]=popgen(n,l)
if show==1 then printf("POPX first\n"), disp(POPX), end
//Compute decimal value ('0' is placed at index '1' !!!)
// Count occurences
for j=1:n
v=POPX(j,:), d = vec2dec(v,l), [POPX(j,l+1)]= d, FX(d+1,2)=FX(d+1,2)+1
end//n
if show==1 then printf("POPX second\n"), disp(POPX), end
end //N
for j=1:r
FX(j,3)=(FX(j,2)/n)/N //Normal frequency
FX(j,4)=(FX(j,2)/n)/(((1/2^l)*N)/100) // Frequency as percentage
end//m
disp(FX)
FREQ1=tabul(FX(:,3))
MEAN1=mean(FREQ1(:,1))
STD1= stdevf(FREQ1(:,1), FREQ1(:,2))
FREQ=tabul(FX(:,4))
MEAN=mean(FREQ(:,1))
STD= stdevf(FREQ(:,1), FREQ(:,2))
MAX=max(FREQ(:,1))
MIN=min(FREQ(:,1))
DIST=MAX-MIN
DIST2=DIST/2
printf("Number of Events n * N = %d\n",n*N)
// Show Plot
// clf(), xdel,
// plot2d(FREQ(:,1), FREQ(:,2))
endfunction
//***************************************************
//Function to compute the frequencies of the elements of a population
// and using a fitness function to compute 'virtual' fitness to compare
// the populations with others by fitness. But the function does not make use of these values.
//
// Input:
// l := length of strings
// n := size of population
// N := number of events
// show := if '1' then display the POPX-matrix
//
// Output:
// FX := Vector of freuencies ordered along the decimal values of a string (1st column)
// FXDif := Vector of Differences compared to theoretical expectation in % (2nd column)
// MEAN := The mean value of the differences
// STD := The standard deviation of the differences
//
// Idea: Generate a sequence of populations, count the occurences, and check the degree of agreement between
// empirical values and theoretica lexpectations
function[FITNESS_ALL_PERC1,DIST2,STD, MEAN, FREQ,STD1, MEAN1, FREQ1,FX, POPX]=frequCheck1(l,n,N,show)
// Install the counters
r= (2^l)
c= 3
FX = zeros(r,c)
FITNESS_ALLLOG1=[]
// Generate an internal index for display
for j=1:r
FX(j,1)=j-1
end
// Generate the populations
for i=1:N
[POPX]=popgen(n,l)
if show==1 then printf("POPX first\n"), disp(POPX), end
//Compute decimal value ('0' is placed at index '1' !!!)
// Count occurences
for j=1:n
v=POPX(j,:),
d = vec2dec(v,l), [POPX(j,l+1)]= d, //decimal values
FX(d+1,2)=FX(d+1,2)+1, //occurences
[POPX(j,l+2)]= fitness1(POPX(j,l+1)) //fitness values
end//n
[FITNESS_ALL]=fitness(POPX,l)
FITNESS_ALLLOG1(i)=FITNESS_ALL
if show==1 then printf("POPX second\n"), disp(POPX), end
end //N
for j=1:r
FX(j,3)=(FX(j,2)/n)/N //Normal frequency
FX(j,4)=(FX(j,2)/n)/(((1/2^l)*N)/100) // Frequency as percentage
end//m
disp(FX)
FREQ1=tabul(FX(:,3))
MEAN1=mean(FREQ1(:,1))
STD1= stdevf(FREQ1(:,1), FREQ1(:,2))
FREQ=tabul(FX(:,4))
MEAN=mean(FREQ(:,1))
STD= stdevf(FREQ(:,1), FREQ(:,2))
MAX=max(FREQ(:,1))
MIN=min(FREQ(:,1))
DIST=MAX-MIN
DIST2=DIST/2
printf("Number of Events n * N = %d\n",n*N)
// Compute the maximal value and the percentage of success
[MAXFIT]=maxfit02(l,n)
FITNESS_ALL_PERC1=[]
for i=1:N, FITNESS_ALL_PERC1(i) = FITNESS_ALLLOG1(i)/(MAXFIT/100), end
// Show graphical results
if show==2 then
clf(), xdel,
plot2d([1:1:N], [FITNESS_ALL_PERC1]),
end
endfunction
//***************************************************
//Function to repeat frequency checks
//
// Input:
// l := length of strings
// n := size of population
// N := Number of events
// K := how often steps should be applied
//
// Output:
// FX := Vector of freuencies ordered along the decimal values of a string (1st column)
// FREQ := Vector of frequencies and their occurences
// MEAN := The mean value of the differences
// STD := The standard deviation of the difference
// DIST2 := Half distances between MAX and MIN
function[MEANX, DIST2X, MEAN1X, STD1X,DIST20, MEAN0]=freqCheckRep(l,n,N,K,show)
// Counter for MEANX, DIST2X...
MEAN1X=[]
STD1X =[]
MEANX=[]
DIST2X =[]
for j=1:K
[DIST2,STD, MEAN, FREQ,STD1, MEAN1, FREQ1,FX, POPX]=frequCheck(l,n,N,show)
MEAN1X(j,1) = MEAN1
STD1X(j,1) = STD1
MEANX(j,1) = MEAN
DIST2X(j,1) = DIST2
end //j
MEAN10 = mean(MEAN1X(:,1))
STD10 = mean(STD1X(:,1))
MEAN0 = mean(MEANX(:,1))
DIST20 = mean(DIST2(:,1))
// Show Plot
// clf(), xdel,
// plot2d([DIST2SUM(:,1)], [DIST2SUM(:,4)])
endfunction
//***************************************************
//Function to repeat frequency checks with gassimple0()
//
// Input:
// l := length of strings
// n := size of population
// N := Number of events
// K := how often steps should be applied
//
// Output:
// FX := Vector of freuencies ordered along the decimal values of a string (1st column)
// FREQ := Vector of frequencies and their occurences
// MEAN := The mean value of the differences
// STD := The standard deviation of the difference
// DIST2 := Half distances between MAX and MIN
function[MEANX, DIST2X, MEAN1X, STD1X,DIST20, MEAN0]=freqCheckRep0(POP,l,p,n,N,K, MThreshold,show)
// Counter for MEANX, DIST2X...
MCount = 0
MEAN1X=[]
STD1X =[]
MEANX=[]
DIST2X =[]
XDIM=[]
for j=1:K
XDIM(j,1)=j*N
[MCount,DIST2,STD, MEAN, FREQ,STD1, MEAN1, FREQ1,POP,FX]=gasimple0(POP,l,p,n,N, j,MThreshold,MCount,show)
disp(MCount)
MEAN1X(j,1) = MEAN1
STD1X(j,1) = STD1
MEANX(j,1) = MEAN
DIST2X(j,1) = DIST2
end //j
MEAN10 = mean(MEAN1X(:,1))
STD10 = mean(STD1X(:,1))
MEAN0 = mean(MEANX(:,1))
DIST20 = mean(DIST2(:,1))
// Show Plot
if show==2 then clf(), xdel, plot2d([XDIM(:,1)], [DIST2X(:,1)]), end
endfunction
//***************************************************
//Function to compute the changing quality of solution sets
//
// Input:
// l := length of strings
// n := size of population
// N := Number of events
// K := how often should be incremented
//
// Output:
// MEAN=:= Mean value of events
// DIST20 := Mean value of 1/2-Distance of events between MAX and MIN
// DIST2X := Series of DIST0s
// MEANX := Series of MEANOs
// FX := Summary of all values
function[MDX]=solutionSetApproach(l,n,N,K,show)
// Counter
MDX=zeros(K,6)
for j=1:K
disp(j)
[DIST2,STD, MEAN, FREQ,STD1, MEAN1, FREQ1,FX, POPX]=frequCheck(l,n,j*N,show)
MDX(j,1) = j*N
MDX(j,2) = MEAN
MDX(j,3) = DIST2
MDX(j,4) = STD
MDX(j,5) = MEAN1
MDX(j,6) = STD1
end //j
// Show Plot
clf(), xdel,
x=[MDX(:,1)],
y1=[MDX(:,3)], subplot(3,1,1)
plot2d(x,y1), xtitle=("DIST2[%]")
y2=[MDX(:,4)],subplot(3,1,2)
plot2d(x,y2), xtitle=("STD[%]")
y3=[MDX(:,6)], subplot(3,1,3)
plot2d(x,y3), xtitle=("STD")
endfunction
//***************************************************
//Function to integrate multiple frequency simulations
//
// Input:
// l := length of strings
// n := size of population
// step := Inrement for number of events
// K := how often steps should be applied
//
// Output:
// DIST2SUM := Summary of distances DIST2 with regard to number of events
function[DIST2SUM]=distSum(l,n,step,K,show)
// Counter for DIST2
DIST2SUM=zeros(K,4)
for j=1:K
disp(j)
[DIST2,STD, MEAN, FREQ,FX, POPX]=frequCheck(l,n,j*step,show)
DIST2SUM(j,1) = j*step
DIST2SUM(j,2) = MEAN
DIST2SUM(j,3) = DIST2
DIST2SUM(j,4) = DIST2SUM(j,3)/(MEAN/100)
end //j
// Show Plot
clf(), xdel,
plot2d([DIST2SUM(:,1)], [DIST2SUM(:,4)])
endfunction
//***************************************************
// Adapt LCS matrices to GA matrices by doubbleing fitness values
// conformFit()
//
// Idea:
// The GA-pop matrices have a fitness value at l+2 based on l+1.
// The LCS-pop matrices have their fitness values at l+1
//
// l := length of fitness strings before fitness
function[CLASSIF,l]=conformFit(CLASSIF)
[r,c]=size(CLASSIF);
l=c-2
// Take every row and compute the fitness as copy of fitness
for j=1:r
CLASSIF(j,l+2)=CLASSIF(j,l+1)
end
endfunction
//***************************************************
//Function to compute the overall fitness of a matrix POP
// Sum up all the l+2-th positions
// l := length of fitness strings
function[FITNESS_ALL]=fitness(POP,l)
FITNESS_ALL=0;
[r,c]=size(POP);
for j=1:r
FITNESS_ALL=FITNESS_ALL+POP(j,l+2)
end
endfunction
//***************************************************
//Function to compute the maximal individual fitness of a matrix POP
// Compute all the l+2-th positions
// l := length of fitness strings
function[MFITNESS]=maxfitness(POP,l)
// Extracts column l+2 and selects the maximal values
MFITNESS = max(POP([:],l+2))
endfunction
//***************************************************
//Function to compute the relative fitness of a string
// along with the average fitness
// Compute all the l+3-th positions
// l := length of fitness strings
function[POP,AFITNESS]=rfitness(POP,l, FITNESS_ALL)
[r,c]=size(POP);
for j=1:r,
if POP(j,l+2)==0 then POP(j,l+2)=POP(j,l+2)+0.0001, end
POP(j,l+3)=POP(j,l+2)/FITNESS_ALL
end
AFITNESS=FITNESS_ALL/r
endfunction
//***************************************************
//Function to compute the fitness ratio r=f1/f0
//
// l := length of fitness strings
// f1 := fitness of all individuals with a allele value '1' at a position
// f0 := fitness of all individuals with a allele value '0' at a position
// r = f1/f0
//
// Assumption: POP has the relativ fitness available at l+3
function[POP,ratio,f1,f0]=fratio10(POP,l,show)
[r,c]=size(POP);
f1=0;
f0=0;
for i=1:r
for j=1:l
if (POP(i,j)== 1) then f1=f1+POP(i,l+3),
else f0=f0+POP(i,l+3)
end
end //j
end//i
ratio=f1/f0
if show == 2 then disp(POP), disp(f1), disp(f0), disp(ratio), end
endfunction
//*************************************************************
// Computing the worst case convergence time tcw
//
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
// POP := a predefined population (can be done automatically)
//
// f1 := fitness of all individuals with a allele value '1' at a position
// f0 := fitness of all individuals with a allele value '0' at a position
// r = f1/f0
// tcw := worst case convergence time
//
// Assumption: POP has the relativ fitness available at l+3
function[POP,tcw,tcabin,ratio,f1,f0]=ftcw(POP,l,p,n,show)
for i=1:n, v=POP(i,:),
d= vec2dec(v,l), //decimal value
[POP(i,l+1)]= d, //decimal value
end
for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end
[FITNESS_ALL]=fitness(POP,l)
[MFITNESS]=maxfitness(POP,l)
[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)
[POP,ratio,f1,f0]=fratio10(POP,l,show)
tcw = log((n-1)^2)/log(ratio)
tcabin = log(n-1)/log(ratio)
endfunction
//***************************************************
//Function to compute the relative count of a string
// along with the realized new count by 'rounding up'
// Compute all the l+4 and l+5-th positions
//
// Problem: if the sum of the new proposals is bigger than n
// Solution:
// l := length of fitness strings
// n := number of individuals in POP
function[POP]=newMember(POP,l,n)
[r,c]=size(POP);
for j=1:r
POP(j,l+4)=POP(j,l+3)*n
POP(j,l+5)=round(POP(j,l+4))
end
//Check for sum of proposals
r2 = 0
for j=1:r, r2=r2+POP(j,l+5), end
while r2>n
z=round(rand()*r)
if z==0 then z=1,end //if
POP(z,l+5) = POP(z,l+5)-1
r2=0, for j=1:r, r2=r2+POP(j,l+5), end//for
end//while r2
endfunction
//***************************************************
// Dummy function to replace newMember in simplegas0
//
// along with the realized new count by 'rounding up'
// Compute all the l+4 and l+5-th positions
// l := length of fitness strings
// n := number of individuals in POP
function[POP]=newMember0(POP,l,n)
[r,c]=size(POP);
for j=1:r
POP(j,l+4)=1
POP(j,l+5)=1
end
endfunction
//***************************************************
// Make a copy of a string from row_old to row_new: L --> R
// where the copy starts at position l+p+1
// l := length of string
// j := row_old
// k := row_new
// p := number of parameters (P=5)
function[POP]=strcpyLR(POP,l,p,j,k)
show=0
[r,c]=size(POP);
// Testing the boundaries
if (j < 1) then if show == 1 then printf('ERROR: Position of old String outside of Matrix! r = %d, j = %d', r,j),end, j=1,
elseif (j > r) then if show == 1 then printf('ERROR: Position of old String outside of Matrix!, r = %d, j = %d', r,j),end, j=r,
elseif (k < 1) then if show == 1 then printf('ERROR: Position of new String outside of Matrix!, r = %d, k = %d', r,k),end, k=1
elseif (k > r) then if show == 1 then printf('ERROR: Position of new String outside of Matrix!, r = %d, k = %d', r,k), end, k=r
end
// Making a copy
for i=1:l
POP(k,l+p+i) = POP(j,i)
end
endfunction
//***************************************************
// Make a copy of a string from row_old to row_new: R --> L
// where the copy starts at position l+p+1
// l := length of string
// j := row_old
// k := row_new
// p := number of parameters (p=5)
function[POP]=strcpyRL(POP,l,p,j,k)
show=0
[r,c]=size(POP);
// Testing the boundaries
if (j < 1) then if show == 1 then printf('ERROR: Position of old String outside of Matrix! r = %d, j = %d', r,j),end, j=1
elseif (j > r) then if show == 1 then printf('ERROR: Position of old String outside of Matrix!, r = %d, j = %d', r,j),end, j=r
elseif (k < 1) then if show == 1 then printf('ERROR: Position of new String outside of Matrix!, r = %d, k = %d', r,k), end, k=1
elseif (k > r) then if show == 1 then printf('ERROR: Position of new String outside of Matrix!, r = %d, k = %d', r,k),end, k=r
end
// Making a copy
for i=1:l
POP(j,i) = POP(k,l+p+i)
end
endfunction
//***************************************************
// Make a copy of all strings from the old rows to the new ones
// where the new copies will start at position l+p+1
// l := length of string
// j := row_old
// k := row_new
// p := number of parameters
// r2 := memory of position for new strings
function[POP]= newPop(POP,l,p,n)
[r,c]=size(POP);
r2 = 1
for j=1:r
if POP(j,l+p) > 0 then r3 = POP(j,l+p)-1,
for k=r2:(r2+r3)
[POP]=strcpyLR(POP,l,p,j,k)
end
r2=k+1
end
end
endfunction
//***************************************************
// Make a copy of all strings from the old rows to the new ones
// where the new copies will start at position l+p+1
//
// Problem: If the sum of new copies is greater than n then this causes a fault!
// Solution: At least check the sum before operation
//
// l := length of string
// j := row_old
// k := row_new
// p := number of parameters
// r2 := memory of position for new strings
function[POP]= newPop2(POP,l,p,n)
[r,c]=size(POP);
//Check for sum of proposals
r2 = 0
for j=1:r, r2=r2+POP(j,l+5), end
if r2 >n then error('In newPop2() sum of proposals >n!!!'),end
r2 = 1
for j=1:r
if POP(j,l+5) > 0 then r3 = POP(j,l+5)-1,
for k=r2:(r2+r3), //printf('\n k = %d\n', k)
[POP]=strcpyLR(POP,l,p,j,k)
end
r2=k+1
end
end
endfunction
//***************************************************
// Prepare the crossover operations within a population POP
// by randomly selecting the new strings and copy them onto the
// POP base area [1,l]
//
// General Assumption: the number of members n is even!!!
//
// The strings are assumed to be in the area starting at l+p+1
// The parameter at l+p has been changed to a flag '1' := not yet mated
// j := target position in the base area for copy action
function[POP]= crossoverPrep(POP,l,p,n)
[r,c]=size(POP);
// Set a flag at position l+7 with '1'
for j=1:r
POP(j,l+7)=1
end
// Select randomly the strings for transfer
j = 1 //:= Baseline for filling up with strings
while(j < n+1)
S = 1 //:= Flag for searching a string to be copied
while(S == 1)
k1 = round(n * rand())
if k1==0 then k1=1
end //if
if POP(k1,l+7) <> 0 then POP=strcpyRL(POP,l,p,j,k1)
//mshow(POP,n,l+p+l)
POP(k1,l+7) = 0,
S=0
else S=1
end //if
end //while == S
// printf('k1 = %d\n',k1)
// printf('j = %d\n',j)
j = j+1
// mshow(POP,n,l+p+l)
end // while == j
endfunction
//***************************************************
// Apply a crossover operation onto two adjacent strings at intersection x
// The strings are assumed to be randomly paired in the area at position 1
//
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
function[POP]= crossover(POP,l,p,n)
// Take a first row
r=1
while(r < n)
// printf('r = %d\n',j)
// Select randomly a point in this row
x = round(l * rand()), if(x == 0) then x=1,end,
// printf('x = %d\n',x)
for i=x:l, m=POP(r+1,i)
POP(r+1,i) = POP(r,i)
POP(r,i) = m
end
r=r+2
end
endfunction
//***************************************************
// Apply a mutation operation onto one randomly selected string
// Select randomly a point in the string and replace it's
// value by it's inverse '1' --> '0', '0' --> '1'
function[POP]= mutation(POP,l,p,n)
// Find a point in a string
c = round(l * rand())
if c == 0 then c=1 // This does not change anything
end
// Find a row in the table
r = round(n * rand())
if r == 0 then r=1 // This does not change anything
end
// replace the value
if(POP(r,c) == 1) then POP(r,c) = 0,
else POP(r,c) = 1
end
printf('mutation point at row = %d col = %d\n',r,c)
endfunction
//***************************************************
// Print the content of a matrix
//
// d := depth of matrix 'downwards'
// w := width of matrix from left to right
function[M]= mshow(M,d,w)
for j=1:d,// printf('\n j= %3.1d : ',j)
for i=1:w, //printf(' %3.1d ',M(j,i))
end
//printf('\n')
end
endfunction
//***************************************************
// Translate strings with binaries '0', '1' as decimal numbers
//
// v = vector of binaries from a POP-matrix (left part)
// l := length of string
// D := decimal computed out of binaries
function[D]= vec2dec(v,l)
str=string(v(1:l))
for i=2:l, str(1)=str(1)+str(i)
end
D=bin2dec(str(1))
endfunction
//***************************************************
// Translate strings with binaries '0', '1' as decimal numbers
//
// v = vector of binaries from a POP-matrix (left part)
// l := length of string
// D := decimal computed out of binaries
function[D]= vec22dec(v,l1,l2)
str=string(v(l1:l2))
for i=2:l2-l1+1, str(1)=str(1)+str(i)
end
D=bin2dec(str(1))
endfunction
//***************************************************
// Translate strings with binaries '0', '1' and n-many compartments as decimal numbers
//
// v = vector of binaries from a POP-matrix (left part)
// l := length of string
// b := number of bins for one number
// D := Array of decimals
function[D]= vec222dec(v,l,b,show)
D=[]
k=1
for j=1:b:l+1-b
if show==1 then printf('j = %d ',j),end
str=string(v(j:j+b-1))
for i=2:b, str(1)=str(1)+str(i)
end //i
if show==1 then printf('k = %d ',k),end
D(k)=bin2dec(str(1))
if show==1 then printf('D(k) = %d\n',D(k)),end
k=k+1
end //j
endfunction
//***************************************************
// maxfit01 builds a string of length l and computes the decimal value
//
// l := length of string
// MF := decimal computed out of binaries
function[MF]= maxfit01(l)
FitString=""
v=ones(1,l)
str=string(v)
for i=1:l, FitString = FitString + str(i)
end
MF=bin2dec(FitString)
endfunction
//***************************************************
// maxfi02 computes with maxfit01 the decimal value of a string with length l and
// then compares the maximal value according to the fitness function y=x^2
// multiplied by the number n of strings in a population
//
// l := length of string
// MF := decimal computed out of binaries
function[MAXFIT]= maxfit02(l,n)
MAXFIT=n*(maxfit01(l)^2)
endfunction
//***************************************************
// Simple fitness-function f=(x^2)
//
// D := decimal computed out of binaries
function[F]= fitness1(D)
F=D^2
endfunction
//***************************************************
// Fitness-function f for a world W which is realized as a table t:D --> R
// IF (d,r) in t then f(d1,d2)=100, ELSE f(d1,d2)=0
//
// d1,d2 := decimal values of population POP
// W := a world organized as a table
// n := number of elements in W
// F := fitness value
function[F]= fitness2(d1,d2,W)
[r,c]=size(W)
upper =10
goal = upper*2
i=1
while i < r+1,
if W(i,1) == d1 & W(i,2) == d2 then F=goal, i=r+1,
else F=round(upper * rand()), i=i+1,
end //if
end//while
endfunction
//***************************************************
// Fitness-function f for a world W which is realized as a table t:D --> R
// IF (d,r) in t then f(d1,d2)=goal, ELSE f(d1,d2)=random(upper)
//
// D := Array of pairs of decimal values
// W := a world organized as a table
// F := fitness value
function[F,goal]= fitness3(D,W)
[r,c]=size(W)
[r2,c2]=size(D)
F2=[]
upper =10 // range of numbers for non-goals [0,upper]
goal = upper*2
j=1 //Index for D
for i=1:r //Look to every pair in W
if W(i,1) == D(j) & W(i,2) == D(j+1) then F2(i)=goal,
else F2(i)=round(upper * rand()),
end //if
j=j+2
end // for i
F=sum(F2)
endfunction
//*************************************************************
// Function to compute only the fitness of a population
//
// Input:
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings
// n := number of elements in POP
// Output
// POP := a population
// MFITNESS := Maximal Fitness of each individual
function[POP,MFITNESS, FITNESS_ALL]=popFit(l,p,n)
[POP]=popgen(n,l+p)
MFITNESS=0
for j=1:n, v=POP(j,:), [POP(j,l+1)]= vec2dec(v,l)
end
for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end
[FITNESS_ALL]=fitness(POP,l)
[MFITNESS]=maxfitness(POP,l)
endfunction
//*************************************************************
// Function to compute the maximal fitness of an individuum
// for several populations
//
// Input:
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings
// n := number of elements in POP
// run := number of choices
// Output
// POP := a population
// MFITNESS := Maximal Fitness of each individual
// MFITNESSX := Array with maximal fitness
function[POP,MEAN, MFITNESSX]=popFitX(l,p,n,run)
MAXFITUP = ((2^l)^2)
for k=1:run
[POP]=popgen(n,l+p)
for j=1:n, v=POP(j,:), [POP(j,l+1)]= vec2dec(v,l)
end
for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end
[MFITNESSX(k)]=maxfitness(POP,l)
end
for k=1:run
MFITNESSX(k)=MFITNESSX(k)/(MAXFITUP/100)
end
MEAN = mean(MFITNESSX)
// Show graphical results
//clf(), xdel,
//plot2d([1:1:run], MFITNESSX)
endfunction
//*************************************************************
// Function to compute the maximal fitness of an individuum
// for several populations
// for increasing n
//
// Input:
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings
// n := number of elements in POP
// run := number of choices
// Output
// POP := a population
// MFITNESS := Maximal Fitness of each individual
// MFITNESSX := Array with maximal fitness
function[MEAN, MEANX]=popFitXN(l,p,m,run)
for i=1:m
[POP,MEAN, MFITNESSX]=popFitX(l,p,i,run)
MEANX(i) = MEAN
end
MEAN = mean(MEANX)
// Show graphical results
clf(), xdel,
plot2d([1:1:m], MEANX)
endfunction
//*************************************************************
// Function to compute the maximal fitness of a population
// for several generations
//
// Input:
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings
// n := number of elements in POP
// run := number of generations
// Output
// POP := a population
// FITNESS_ALL := Maximal Fitness of a population
// FITNESS_ALLX := Array with maximal fitness
// MEAN := Mean value of array
function[STD,MEAN, FITNESS_ALLX]=popMaxFitX(l,p,n,run)
MAXFITUP = ((2^l)^2)*n
for k=1:run
[POP]=popgen(n,l+p)
for j=1:n, v=POP(j,:), [POP(j,l+1)]= vec2dec(v,l)
end
for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end
[FITNESS_ALLX(k)]=fitness(POP,l)
end
for k=1:run
FITNESS_ALLX(k)=FITNESS_ALLX(k)/(MAXFITUP/100)
end
MEAN = mean(FITNESS_ALLX)
mf=tabul(FITNESS_ALLX)
STD=stdevf(mf([:],1), mf([:],2))
// Show graphical results
//clf(), xdel,
//plot2d([1:1:run], MFITNESSX)
endfunction
//*************************************************************
// All Functions Unified
//
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
// POP := a predefined population (can be done automatically)
// run := number of cycles
// MThreshold := number of cycles which have to be waited until the mutation operators will be applied
function[POP,FITNESS_ALLLOG]=gasimple(POP,l,p,n,run, MThreshold)
MCount = 0
FITNESS_ALLLOG=[]
for cyc = 1:run
[M]= mshow(POP,n,l+p)
for j=1:n, v=POP(j,:), [POP(j,l+1)]= vec2dec(v,l)
end
for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end
[FITNESS_ALL]=fitness(POP,l)
FITNESS_ALLLOG(cyc)=FITNESS_ALL
[MFITNESS]=maxfitness(POP,l)
[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)
[POP]=newMember(POP,l,n)
[POP]=newPop(POP,l,p,n)
[POP]= crossoverPrep(POP,l,p,n)
[POP]= crossover(POP,l,p,n)
printf('Mutationcount = %d\n', MCount)
if(MCount > MThreshold) then [M]= mshow(POP,n,l+p),
[POP]= mutation(POP,l,p,n),
[M]= mshow(POP,n,l+p),
MCount=0,
end
MCount = MCount + 1
end //for == run
// Compute the maximal value and the percentage of success
[MAXFIT]=maxfit02(l,n)
FITNESS_ALL_PERC=[]
for i=1:run, FITNESS_ALL_PERC(i) = FITNESS_ALLLOG(i)/(MAXFIT/100), end
// Show graphical results
clf(), xdel,
//plot2d([1:1:run], FITNESS_ALLLOG)
plot2d([1:1:run], FITNESS_ALL_PERC)
endfunction
//*************************************************************
// A system with GA without any additional parameters
//
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
// POP := a predefined population (can be done automatically)
// N := number of cycles
// MThreshold := number of cycles which have to be waited until the mutation operators will be applied
function[FITNESS_ALL_PERC,POP]=ga(POP,l,p,n,N, MThreshold,show)
MCount = 0
FITNESS_ALLLOG=[]
for cyc = 1:N
for j=1:n, v=POP(j,:),
d= vec2dec(v,l), //decimal value
[POP(j,l+1)]= d, //decimal value
end
for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end
[FITNESS_ALL]=fitness(POP,l)
FITNESS_ALLLOG(cyc)=FITNESS_ALL
[MFITNESS]=maxfitness(POP,l)
[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)
[POP]=newMember(POP,l,n)
[POP]=newPop(POP,l,p,n)
[POP]= crossoverPrep(POP,l,p,n)
[POP]= crossover(POP,l,p,n)
if show==1 then
printf('Mutationcount = %d\n', MCount),
end
if(MCount > MThreshold) then
[POP]= mutation(POP,l,p,n),
if show==1 then disp(POP), end
MCount=0,
end
MCount = MCount + 1
end //for == N
printf("Number of Events n * N = %d\n",n*N)
// Compute the maximal value and the percentage of success
[MAXFIT]=maxfit02(l,n)
FITNESS_ALL_PERC=[]
for i=1:N, FITNESS_ALL_PERC(i) = FITNESS_ALLLOG(i)/(MAXFIT/100), end
// Show graphical results
if show==2 then
clf(), xdel,
plot2d([1:1:N], FITNESS_ALL_PERC),
end
endfunction
//*************************************************************
// A system with GA
//
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
// POP := a predefined population (can be done automatically)
// N := number of cycles
// MThreshold := number of cycles which have to be waited until the mutation operators will be applied
function[FITNESS_ALL_PERC,DIST2,STD, MEAN, FREQ,STD1, MEAN1, FREQ1,FX, POP]=ga0(POP,l,p,n,N, MThreshold,show)
// Install the counters
r= (2^l)
c= 6
FX = zeros(r,c)
MCount = 0
FITNESS_ALLLOG=[]
// Generate an internal index for display
for j=1:r
FX(j,1)=j-1
end
for cyc = 1:N
for j=1:n, v=POP(j,:),
d= vec2dec(v,l), //decimal value
[POP(j,l+1)]= d, //decimal value
FX(d+1,2)=FX(d+1,2)+1, //occurences
end
for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end
[FITNESS_ALL]=fitness(POP,l)
FITNESS_ALLLOG(cyc)=FITNESS_ALL
[MFITNESS]=maxfitness(POP,l)
[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)
[POP]=newMember(POP,l,n)
[POP]=newPop(POP,l,p,n)
[POP]= crossoverPrep(POP,l,p,n)
[POP]= crossover(POP,l,p,n)
if show==1 then
printf('Mutationcount = %d\n', MCount),
end
if(MCount > MThreshold) then
[POP]= mutation(POP,l,p,n),
if show==1 then disp(POP), end
MCount=0,
end
MCount = MCount + 1
end //for == N
for j=1:r
FX(j,3)=(FX(j,2)/n)/N //Normal frequency
FX(j,4)=(FX(j,2)/n)/(((1/2^l)*N)/100) // Frequency as percentage
end//m
disp(FX)
FREQ1=tabul(FX(:,3))
MEAN1=mean(FREQ1(:,1))
STD1= stdevf(FREQ1(:,1), FREQ1(:,2))
FREQ=tabul(FX(:,4))
MEAN=mean(FREQ(:,1))
STD= stdevf(FREQ(:,1), FREQ(:,2))
MAX=max(FREQ(:,1))
MIN=min(FREQ(:,1))
DIST=MAX-MIN
DIST2=DIST/2
printf("Number of Events n * N = %d\n",n*N)
// Compute the maximal value and the percentage of success
[MAXFIT]=maxfit02(l,n)
FITNESS_ALL_PERC=[]
for i=1:N, FITNESS_ALL_PERC(i) = FITNESS_ALLLOG(i)/(MAXFIT/100), end
// Show graphical results
if show==2 then
clf(), xdel,
plot2d([1:1:N], FITNESS_ALL_PERC),
end
endfunction
//*************************************************************
// GA algorithm without fitness
//
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
// POP := a predefined population (can be done automatically)
// N := number of events
// K := Number of repetitions from calling function
// MThreshold := number of events which have to be waited until the mutation operators will be applied
function[MCount,DIST2,STD, MEAN, FREQ,STD1, MEAN1, FREQ1,POP,FX]=gasimple0(POP,l,p,n,N, K,MThreshold,MCount,show)
// Install the counters
r= (2^l)
c= 5
FX = zeros(r,c)
// Generate an internal index for display
for j=1:r
FX(j,1)=j-1
end
for cyc = 1:N*K //Start Cyle for events
if show ==1 then disp(cyc), end
for j=1:n
v=POP(j,:), d = vec2dec(v,l), [POP(j,l+1)]= d, FX(d+1,2)=FX(d+1,2)+1
end//n
if show ==1 then printf("\nFX after Count\n\n"), disp(FX), end
[POP]=newMember0(POP,l,n) //Prepares copies by inserting '1' at position l+4 and l+5
[POP]=newPop(POP,l,p,n) //Copies old strings to the right
[POP]= crossoverPrep(POP,l,p,n)
[POP]= crossover(POP,l,p,n)
if show ==1 then printf('Mutationcount = %d\n', MCount),disp(POP), end
if(MCount > MThreshold) then [POP]= mutation(POP,l,p,n),
if show ==2 then printf('Mutationcount (MCount, cyc)= (%d,%d)\n', MCount, cyc), end
MCount = 0, end
MCount = MCount + 1
if show==1 then printf("POP after Operators\n"), disp(POP), end
end //cyc=N
for j=1:r
FX(j,3)=(FX(j,2)/n)/(N*K) //Normal frequency
FX(j,4)=(FX(j,2)/n)/(((1/2^l)*(N*K))/100) // Frequency as percentage
end//m
disp(FX)
FREQ1=tabul(FX(:,3))
MEAN1=mean(FREQ1(:,1))
STD1= stdevf(FREQ1(:,1), FREQ1(:,2))
FREQ=tabul(FX(:,4))
MEAN=mean(FREQ(:,1))
STD= stdevf(FREQ(:,1), FREQ(:,2))
MAX=max(FREQ(:,1))
MIN=min(FREQ(:,1))
DIST=MAX-MIN
DIST2=DIST/2
printf("Number of Events n * N * K = %d\n",n*N*K)
endfunction
//*************************************************************
// GA algorithm with fitness and conditioned mutation
//
// Works like 'normal' GA but uses mutation only if the actual maximal fitness
// stays 'constant' over MT-many cycles and is below te theoretical maximum
//
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
// POP := a predefined population (can be done automatically)
// N := number of events
// MT := mutation trigger; number of values to monitor for to trigger mutation
function[FITNESS_ALL_PERC,DIST2,STD, MEAN, FREQ,STD1, MEAN1, FREQ1,FX, POP]=ga1(POP,l,p,n,N, MT,show)
//Theoretical Maximum for Fitness according to y=x^2
TMaxFit = ((2^l)-1)^2*n
// Install the counters
r= (2^l)
c= 6
FX = zeros(r,c)
MCount = 0
FITNESS_ALLLOG=[]
MTriggerEstimator=[]
// Generate an internal index for display
for j=1:r
FX(j,1)=j-1
end
for cyc = 1:N
for j=1:n, v=POP(j,:),
d= vec2dec(v,l), //decimal value
[POP(j,l+1)]= d, //decimal value
FX(d+1,2)=FX(d+1,2)+1, //occurences
end
for i=1:n,[POP(i,l+2)]= fitness1(POP(i,l+1))
end
[FITNESS_ALL]=fitness(POP,l)
FITNESS_ALLLOG(cyc)=FITNESS_ALL
[MFITNESS]=maxfitness(POP,l)
if show ==1 then disp(FITNESS_ALL), end
MTriggerEstimator(cyc)=FITNESS_ALL
if show ==1 then disp(MTriggerEstimator(cyc)), end
[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)
[POP]=newMember(POP,l,n)
[POP]=newPop(POP,l,p,n)
[POP]= crossoverPrep(POP,l,p,n)
[POP]= crossover(POP,l,p,n)
if show ==1 then disp(MCount), end
if(MCount > MT) then
if show ==1 then disp(MTriggerEstimator(cyc)), disp(MTriggerEstimator(cyc-MT)), disp(TMaxFit), end
if (MTriggerEstimator(cyc) == MTriggerEstimator(cyc-MT) & MTriggerEstimator(cyc) < TMaxFit) then [POP]= mutation(POP,l,p,n),
if show==1 then disp(POP), end
end
MCount=0,
end
MCount = MCount + 1
end //for == N
for j=1:r
FX(j,3)=(FX(j,2)/n)/N //Normal frequency
FX(j,4)=(FX(j,2)/n)/(((1/2^l)*N)/100) // Frequency as percentage
end//m
disp(FX)
FREQ1=tabul(FX(:,3))
MEAN1=mean(FREQ1(:,1))
STD1= stdevf(FREQ1(:,1), FREQ1(:,2))
FREQ=tabul(FX(:,4))
MEAN=mean(FREQ(:,1))
STD= stdevf(FREQ(:,1), FREQ(:,2))
MAX=max(FREQ(:,1))
MIN=min(FREQ(:,1))
DIST=MAX-MIN
DIST2=DIST/2
printf("Number of Events n * N = %d\n",n*N)
// Compute the maximal value and the percentage of success
[MAXFIT]=maxfit02(l,n)
FITNESS_ALL_PERC=[]
for i=1:N, FITNESS_ALL_PERC(i) = FITNESS_ALLLOG(i)/(MAXFIT/100), end
// Show graphical results
if show==2 then
clf(), xdel,
plot2d([1:1:N], FITNESS_ALL_PERC),
end
endfunction
//*************************************************************
// A system with GA for a world with a table
//
// A world W organized as a table maps a set D into a set R
// l := length of strings
// p := number of cells between string <1...l> and <l+p+1, ..., l+p+l>
// Pos 1-l := String
// Pos l+1 := Decimal Value of binary string
// Pos l+2 := Fitness for l+1 and l+p
// Pos l+3 := Percentage of overall fitness
// Pos l+4 := Expected count according to fitness
// Pos l+5 := Realized count
// Pos l+6 := 2nd Decimal value of a compund fitness
// Pos l+p := flag for crossover
// p := 7
// POP := a predefined population (can be done automatically)
// n := number of elements in POP
// N := number of cycles
// MT := number of cycles which have to be waited until the mutation operators will be applied
function[FITNESS_ALL_PERC,POP]=gaw1(W,POP,l,p,n,N, MT,l1,show)
MCount = 0
FITNESS_ALLLOG=[]
for cyc = 1:N
if show == 1 then disp('cyc ='),disp(cyc),disp(' '),end
for j=1:n, v=POP(j,:),
d1= vec22dec(v,1,l1), //decimal value1
d2= vec22dec(v,l1+1,l), //decimal value2
[POP(j,l+1)]= d1, //decimal value
[POP(j,l+6)]= d2, //decimal value
end
if show == 1 then printf('New Numbers in POP '), disp(POP), end
for i=1:n,[POP(i,l+2)]= fitness2(POP(i,l+1),POP(i,l+6),W)
end
[FITNESS_ALL]=fitness(POP,l)
if show == 1 then printf('FITNESS_ALL = %f\n',FITNESS_ALL), end
FITNESS_ALLLOG(cyc)=FITNESS_ALL
[MFITNESS]=maxfitness(POP,l)
[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)
if show == 1 then disp(POP), end
[POP]=newMember(POP,l,n)
[POP]=newPop2(POP,l,p,n)
if show == 1 then disp(POP), end
[POP]= crossoverPrep(POP,l,p,n)
[POP]= crossover(POP,l,p,n)
if show == 1 then disp(POP),printf('MCount = %d\n',MCount), end
if(MCount > MT) then
[POP]= mutation(POP,l,p,n), printf('Mutation at cycle = %d\n',cyc),
if show==1 then disp(POP), end
MCount=0,
end
MCount = MCount + 1
end //for == N
printf("Number of Events n * N = %d\n",n*N)
// Compute the maximal value and the percentage of success
MAXFIT=20*n //The value '20' is set in the function fitness2()
FITNESS_ALL_PERC=[]
for i=1:N, FITNESS_ALL_PERC(i) = FITNESS_ALLLOG(i)/(MAXFIT/100), end
// Show graphical results
if show==2 | show == 1 then
clf(), xdel,
plot2d([1:1:N], FITNESS_ALL_PERC),
end
endfunction
//*************************************************************
// A system with GA for a world with a table
//
// A world W organized as a table maps a set D into a set R
// l := length of strings
// p := number of cells between string <1...l> and <l+p+1, ..., l+p+l>
// Pos 1-l := String
// Pos l+1 := Decimal Value of binary string
// Pos l+2 := Fitness for l+1 and l+p
// Pos l+3 := Percentage of overall fitness
// Pos l+4 := Expected count according to fitness
// Pos l+5 := Realized count
// Pos l+6 := 2nd Decimal value of a compund fitness
// Pos l+7 := flag for crossover
// p := 7
// POP := a predefined population (can be done automatically)
// n := number of elements in POP
// N := number of cycles
// MT := number of cycles which have to be waited until the mutation operators will be applied
// b := number of bins for one number
// V := version
function[FITNESS_ALL_PERC,MAXGENOMECOUNT,POP,V]=gaw2(W,POP,l,n,N, MT,b,show,V)
p = 7
MCount = 0
FITNESS_ALLLOG=[]
for cyc = 1:N
if show == 1 then disp('cyc ='),disp(cyc),disp(' '),end
for i=1:n , v=POP(i,:), [D]= vec222dec(v,l,b,show), [POP(i,l+2),goal]= fitness3(D,W), end //for i
if show == 1 then printf('New Numbers in POP '), disp(POP), end
[FITNESS_ALL]=fitness(POP,l)
if show == 1 then printf('FITNESS_ALL = %f\n',FITNESS_ALL), end
FITNESS_ALLLOG(cyc)=FITNESS_ALL
[MFITNESS]=maxfitness(POP,l)
[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)
// if show == 1 then disp(POP), end
[POP]=newMember(POP,l,n)
if show == 1 then disp(POP), end
[POP]=newPop2(POP,l,p,n)
if show == 1 then disp(POP), end
[POP]= crossoverPrep(POP,l,p,n)
[POP]= crossover(POP,l,p,n)
if show == 1 then disp(POP),printf('MCount = %d\n',MCount), end
if(MCount > MT) then
[POP]= mutation(POP,l,p,n), printf('Mutation at cycle = %d\n',cyc),
if show==1 then disp(POP), end
MCount=0,
end
MCount = MCount + 1
end //for == N
printf("Number of Events n * N = %d\n",n*N)
// Compute the maximal value and the percentage of success
[r,c]=size(POP)
[r2,c2]=size(W)
MAXFIT=goal*r2*r //The value 'goal' is set in the function fitness3()
MAXFITGENOME = goal*r2 // To count the complete genomes in a population
FITNESS_ALL_PERC=[]
MAXGENOMECOUNT = 0
for i=1:r,
if POP(i,l+2) == MAXFITGENOME then MAXGENOMECOUNT =MAXGENOMECOUNT+1, end,
end
for i=1:N, FITNESS_ALL_PERC(i,1)=i, FITNESS_ALL_PERC(i,2) = FITNESS_ALLLOG(i)/(MAXFIT/100), end
// Show graphical results
if show==2 | show == 1 then
clf(), xdel,
scf(V),
plot2d([1:1:N], FITNESS_ALL_PERC(:,2)),
end
endfunction
//*************************************************************
// Computing the worst case convergence time tcw
//
// p := number of parameters between strings left and right (actually p=5)
// l := length of strings ( actually l=5)
// n := number of elements in POP (actually n=4)
// POP := a predefined population (can be done automatically)
//
// f1 := fitness of all individuals with a allele value '1' at a position
// f0 := fitness of all individuals with a allele value '0' at a position
// r = f1/f0
// tcw := worst case convergence time
//
// Assumption: POP has the relativ fitness available at l+3
function[POP,tcw,tcabin,ratio,f1,f0]=ftcw2(W,POP,l,p,n,l1,show)
for j=1:n, v=POP(j,:),
d1= vec22dec(v,1,l1), //decimal value1
d2= vec22dec(v,l1+1,l), //decimal value2
[POP(j,l+1)]= d1, //decimal value
[POP(j,l+6)]= d2, //decimal value
end
for i=1:n,[POP(i,l+2)]= fitness2(POP(i,l+1),POP(i,l+6),W)
end
[FITNESS_ALL]=fitness(POP,l)
[MFITNESS]=maxfitness(POP,l)
[POP,AFITNESS]=rfitness(POP,l,FITNESS_ALL)
[POP,ratio,f1,f0]=fratio10(POP,l,show)
tcw = log((n-1)^2)/log(ratio)
tcabin = log(n-1)/log(ratio)
endfunction
//***********************************************************************
// Examples
//
POP = [0 1 1 0 1 13 169 0 0 0; 1 1 0 0 0 24 576 0 0 0; 0 1 0 0 0 8 64 0 0 0; 1 0 0 1 1 19 361 0 0 0;]
W=[1 3; 2 1; 3 2]
W2=[1 3; 2 1; 3 2; 4 4; 5 7; 6 5]
W3=['_' '_' '_'; '_' '_' '_'; '_' '_' '_']