selection

1 """ 2 selection 3 ========= 4 Contains methods to select individuals from a population. 5 So far fittest selection and tournament selection are supported. 6 7 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 8 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 9 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 10 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 11 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 12 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 13 THE SOFTWARE. 14 15 @author: by Mehdi Khoury 16 @version: 1.20 17 @copyright: (c) 2009 Mehdi Khoury under the mit license 18 http://www.opensource.org/licenses/mit-license.html 19 @contact: mehdi.khoury at gmail.com 20 """ 21 22 import timeit 23 import evalfitness 24 import cPickle 25 from pysqlite2 import dbapi2 as sqlite 26 import psyco 27 import random 28 import operator 29 import copy 30 import wchoice 31 psyco.profile() 32 33 34

35 -def GetDBKeysAndFitness(dbname,tablename):

36 """ 37 Function: GetDBKeysAndFitness 38 ============================== 39 the list of fitnesses with associated unique ids obtained 40 from the database. A lengthy operation. Should be only called once 41 and used as an argument for the tournament or fitness selection functions. 42 43 @param dbname: path to database e.g. r'D:\3d_work\pythongp\pySTGP_0.51\src\pop_db' 44 @param tablename: name of the databse table 45 46 returns: the list of fitnesses with associated unique ids obtained 47 from the database 48 49 """ 50 con = sqlite.connect(dbname) 51 #SELECT = "select o_id, fitness from %s order by fitness" %tablename 52 SELECT = "select o_id, fitness from %s" %tablename 53 cur = con.cursor() 54 cur.execute(SELECT) 55 con.commit() 56 result= cur.fetchall() 57 con.close() 58 sorted_result=sorted(result, key=operator.itemgetter(1)) 59 return sorted_result

60 61 62

63 -def SelectFileFittest(pop_file):

64 """ 65 Function: SelectFileFittest 66 ============================ 67 Select the fittest individual from a file 68 69 @param pop_file: population file 70 71 returns: the reference of one selected individual with 72 73 """ 74 # read the content of the file and evaluate add the fitness of each element in a list 75 fileinput = open(pop_file,'rb') 76 u = cPickle.Unpickler(fileinput) 77 78 temp=u.load() 79 result=[] 80 # evaluate fitess of each element and store in in a list 81 while temp: 82 result.append(evalfitness.EvalFitness().FinalFitness(evalfitness.EvalFitness().EvalTreeForAllInputSets(temp,xrange(2)))) 83 try: 84 temp=u.load() 85 except: 86 break 87 fileinput.close() 88 # select 'size' random indexes of elements 89 mysample=xrange(len(result)) 90 # create the corresponding list of associated fitnesses 91 mysample_fitnesses=[result[el] for el in mysample] 92 ref_sample=[] 93 # asssociate both in one data structure 94 for i in xrange(len(mysample)): 95 ref_sample.append((mysample[i],mysample_fitnesses[i])) 96 # sort them by fitness score 97 ref_sample=sorted(ref_sample, key=operator.itemgetter(1)) 98 selected_individual=ref_sample[0] 99 #print selected_individual 100 return selected_individual

101

102 -def SelectDBOneFittest(db_list):

103 """ 104 Function: SelectDBOneFittest 105 ============================= 106 Select fittest individual 107 108 @param db_list: the ordered list of fitnesses with associated unique ids obtained from the database 109 110 returns: the reference of the one fittest individual 111 112 """ 113 return db_list[0]

114

115 -def SelectDBSeveralFittest(n, db_list):

116 """ 117 Function: SelectDBSeveralFittest 118 ================================= 119 Select n fittest individual 120 121 @param n: the number of fittest individuals 122 @param db_list: the ordered list of fitnesses with associated unique ids obtained from the database 123 124 @return: the reference of the one fittest individual 125 126 """ 127 return db_list[:n]

128 129 130 131 132 133 134

135 -def TournamentSelectFileOne(size, pop_file,prob_selection_fittest):

136 """ 137 Function: SelectFileOne 138 ======================== 139 Select one individual from a file using Tournament selection 140 appropriate and fast when using a small population (<=1000) 141 142 @param size: number of individual choosen at random from the population 143 @param pop_file: population file 144 @param prob_selection_fittest: prob of selecting the fittest of the group 145 146 @return: the reference of one selected individual with 147 prob of choosing fittest=p 148 prob of choosing second fittest= p*(1-p) 149 prob of choosing third fittest= p*((1-p)^2)... 150 151 """ 152 # read the content of the file and evaluate add the fitness of each element in a list 153 fileinput = open(pop_file,'rb') 154 u = cPickle.Unpickler(fileinput) 155 156 temp=u.load() 157 result=[] 158 # evaluate fitess of each element and store in in a list 159 while temp: 160 result.append(evalfitness.EvalFitness().FinalFitness(evalfitness.EvalFitness().EvalTreeForAllInputSets(temp,xrange(2)))) 161 try: 162 temp=u.load() 163 except: 164 break 165 fileinput.close() 166 # select 'size' random indexes of elements 167 mysample=random.sample(xrange(len(result)), size) 168 # create the corresponding list of associated fitnesses 169 mysample_fitnesses=[result[el] for el in mysample] 170 ref_sample=[] 171 # asssociate both in one data structure 172 for i in xrange(len(mysample)): 173 ref_sample.append((mysample[i],mysample_fitnesses[i])) 174 # sort them by fitness score 175 ref_sample=sorted(ref_sample, key=operator.itemgetter(1)) 176 prob_selection=prob_selection_fittest 177 # if probability of choosing fittest = 1 return fittest 178 if prob_selection==1: 179 selected_individual=ref_sample[0] 180 # otherwise choose one element regarding the probability 181 # prob of choosing fittest=p 182 # prob of choosing second fittest= p*(1-p) 183 # prob of choosing third fittest= p*((1-p)^2)... 184 else: 185 selection= [prob_selection*((1-prob_selection)**x) for x in xrange(1,len(ref_sample))] 186 selection.insert(0,prob_selection) 187 wc= wchoice.wchoice(ref_sample, selection, True, True) 188 selected_individual= [wc() for _ in xrange(1)] 189 #print selected_individual 190 return selected_individual

191

192 -def TournamentSelectDBOne(size, prob_selection,db_list):

193 """ 194 Function: SelectDBOne 195 ====================== 196 Select one individual from a database using Tournament selection 197 198 @param size: number of individual choosen at random from the population 199 @param prob_selection: prob of selecting the fittest of the group 200 @param db_list: the list of fitnesses with associated unique ids obtained from the database 201 202 @return: the reference of one selected individual with 203 prob of choosing fittest=p 204 prob of choosing second fittest= p*(1-p) 205 prob of choosing third fittest= p*((1-p)^2)... 206 207 """ 208 209 ref_sample=random.sample(db_list, size) 210 ref_sample=sorted(ref_sample, key=operator.itemgetter(1)) 211 #print ref_sample 212 if prob_selection==1: 213 selected_individual=[ref_sample[0]] 214 else: 215 selection= [prob_selection*((1-prob_selection)**x) for x in xrange(1,len(ref_sample))] 216 selection.insert(0,prob_selection) 217 #print selection 218 wc= wchoice.wchoice(ref_sample, selection, False, True) 219 selected_individual= [wc() for _ in xrange(1)] 220 #print selected_individual 221 return selected_individual

222

223 -def TournamentSelectDBSeveral(nb_outputs, size, prob_selection,db_list):

224 """ 225 Function: SelectDBSeveral 226 ========================== 227 Select one individual from a database using Tournament selection 228 229 @param nb_outputs: repeat the tournament selection nb_outputs times, to 230 return a list nb_outputs selected individuals 231 @param size: number of individual choosen at random from the population 232 @param prob_selection: prob of selecting the fittest of the group 233 @param db_list: the list of fitnesses with associated unique ids obtained from the database 234 235 @return: return a list nb_outputs of references of individuals selected by 236 tournament 237 """ 238 239 240 selection_result=[] 241 i=0 242 while i<nb_outputs: 243 ref_sample=random.sample(db_list, size) 244 ref_sample=sorted(ref_sample, key=operator.itemgetter(1)) 245 #print ref_sample 246 if prob_selection==1: 247 selected_individual=[ref_sample[0]] 248 else: 249 selection= [prob_selection*((1-prob_selection)**x) for x in xrange(1,len(ref_sample))] 250 selection.insert(0,prob_selection) 251 #print selection 252 wc= wchoice.wchoice(ref_sample, selection, False, True) 253 selected_individual= [wc() for _ in xrange(1)] 254 selection_result.append(selected_individual[0]) 255 i=i+1 256 ##print selected_individual 257 return selection_result

258 259 260 261 262 if __name__ == '__main__': 263 #dbname=r'D:\3d_work\pythongp\pySTGP_0.51\src\pop_db' 264 dbname=r'D:\mehdi\python projects\pySTGP_0.52\src\pop_db' 265 tablename='tab1' 266 #writepop.ClearDBTable(r'D:\3d_work\pythongp\pySTGP_0.51\src\pop_db','tab1') 267 #writepop.WriteInitialPopulation2DB(100,(0,2,'root'),2,10,'AddHalfNode',dbname,tablename) 268 #writepop.WriteInitialPopulation2File(100,2,2,10,'AddHalfNode','pop') 269 db_list=GetDBKeysAndFitness(dbname,tablename) 270 271 chosen_one1=TournamentSelectFileOne(7,'pop', 0.8) 272 chosen_one2=TournamentSelectDBOne(7, 0.8,db_list) 273 chosen_one3=TournamentSelectDBSeveral(20,7, 0.8,db_list) 274 chosen_one4= SelectFileFittest('pop') 275 chosen_one5=SelectDBOneFittest(db_list) 276 chosen_one6=SelectDBSeveralFittest(5,db_list) 277 #print db_list 278 #print chosen_one1 279 #print chosen_one2 280 #print chosen_one3 281 #print chosen_one4 282 #print chosen_one5 283 #print chosen_one6 284 285 t1 = timeit.Timer('chosen_one=selection.GetDBKeysAndFitness(dbname,tablename)', 'from __main__ import dbname, tablename,db_list ;import selection') 286 t2 = timeit.Timer('chosen_one=selection.TournamentSelectDBSeveral(20,7, 0.8,db_list)', 'from __main__ import dbname, tablename,db_list ;import selection') 287 t3 = timeit.Timer('chosen_one=selection.TournamentSelectDBOne(7, 0.8,db_list)', 'from __main__ import dbname, tablename ,db_list;import selection') 288 t4 = timeit.Timer('chosen_one=selection.SelectFileFittest(\'pop\')', 'from __main__ import dbname, tablename,db_list ;import selection') 289 t5 = timeit.Timer('chosen_one=selection.SelectDBOneFittest(db_list)', 'from __main__ import dbname, tablename,db_list ;import selection') 290 t6 = timeit.Timer('chosen_one=selection.SelectDBSeveralFittest(5,db_list)', 'from __main__ import dbname, tablename ,db_list;import selection') 291 292 #print t.timeit(100) 293 #print t3.repeat(1,10000) 294

Source Code for Module selection