source: trunk/optimizer/src/pgapack/pgapack/source/duplcate.c @ 816

Last change on this file since 816 was 816, checked in by liveletlive, 15 years ago

Committing the newer version of PGAPack.

File size: 9.5 KB
Line 
1/*
2 * 
3 *  *********************************************************************
4 *  (C) COPYRIGHT 1995 UNIVERSITY OF CHICAGO
5 *  *********************************************************************
6 * 
7 *  This software was authored by
8 * 
9 *  D. Levine
10 *  Mathematics and Computer Science Division Argonne National Laboratory
11 *  Argonne IL 60439
12 *  levine@mcs.anl.gov
13 *  (708) 252-6735
14 *  (708) 252-5986 (FAX)
15 * 
16 *  with programming assistance of participants in Argonne National
17 *  Laboratory's SERS program.
18 * 
19 *  This program contains material protectable under copyright laws of the
20 *  United States.  Permission is hereby granted to use it, reproduce it,
21 *  to translate it into another language, and to redistribute it to
22 *  others at no charge except a fee for transferring a copy, provided
23 *  that you conspicuously and appropriately publish on each copy the
24 *  University of Chicago's copyright notice, and the disclaimer of
25 *  warranty and Government license included below.  Further, permission
26 *  is hereby granted, subject to the same provisions, to modify a copy or
27 *  copies or any portion of it, and to distribute to others at no charge
28 *  materials containing or derived from the material.
29 * 
30 *  The developers of the software ask that you acknowledge its use in any
31 *  document referencing work based on the  program, such as published
32 *  research.  Also, they ask that you supply to Argonne National
33 *  Laboratory a copy of any published research referencing work based on
34 *  the software.
35 * 
36 *  Any entity desiring permission for further use must contact:
37 * 
38 *  J. Gleeson
39 *  Industrial Technology Development Center Argonne National Laboratory
40 *  Argonne IL 60439
41 *  gleesonj@smtplink.eid.anl.gov
42 *  (708) 252-6055
43 * 
44 *  ********************************************************************
45 *  DISCLAIMER
46 * 
47 *  THIS PROGRAM WAS PREPARED AS AN ACCOUNT OF WORK SPONSORED BY AN AGENCY
48 *  OF THE UNITED STATES GOVERNMENT.  NEITHER THE UNIVERSITY OF CHICAGO,
49 *  THE UNITED STATES GOVERNMENT NOR ANY OF THEIR EMPLOYEES MAKE ANY
50 *  WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL LIABILITY OR
51 *  RESPONSIBILITY FOR THE ACCURACY, COMPLETENESS, OR USEFULNESS OF ANY
52 *  INFORMATION OR PROCESS DISCLOSED, OR REPRESENTS THAT ITS USE WOULD NOT
53 *  INFRINGE PRIVATELY OWNED RIGHTS.
54 * 
55 *  **********************************************************************
56 *  GOVERNMENT LICENSE
57 * 
58 *  The Government is granted for itself and others acting on its behalf a
59 *  paid-up, non-exclusive, irrevocable worldwide license in this computer
60 *  software to reproduce, prepare derivative works, and perform publicly
61 *  and display publicly.
62 */
63
64/*****************************************************************************
65*     FILE: duplicate.c: This file contains the routines that have to do with
66*                        testing for duplicate strings
67*
68*     Authors: David M. Levine, Philip L. Hallstrom, David M. Noelle,
69*              Brian P. Walenz
70*****************************************************************************/
71
72#include "pgapack.h"
73
74/*U****************************************************************************
75  PGADuplicate - determines if a specified string is a duplicate of one
76  already in an existing population
77
78  Category: Generation
79
80  Inputs:
81     ctx  - context variable
82     p    - string index
83     pop1 - symbolic constant of the population containing string p
84     pop2 - symbolic constant of the (possibly partial) population containing
85            strings to compare string p against
86     n    - the number of strings in pop2 to compare string p against
87            (indexed 0,...,n-1)
88
89  Outputs:
90     Returns PGA_TRUE if PGAGetNoDuplicates() returns PGA_TRUE and
91     string p in population pop1 is a duplicate of at least one strings
92     0,...,n-1 in population pop2.  Otherwise returns PGA_FALSE
93
94  Example:
95     Change any string in PGA_NEWPOP that is an exact copy of a string
96     in PGA_OLDPOP.
97
98     PGAContext *ctx;
99     int b, n;
100     :
101     n  = PGAGetPopsize(ctx);
102     for (b=0; b<n; b++)
103         if (PGADuplicate(ctx, b, PGA_NEWPOP, PGA_OLDPOP, n))
104             PGAChange(ctx, b, PGA_NEWPOP);
105
106
107     Check if the best string in population PGA_OLDPOP is a duplicate of any
108     of the strings in the first half of population PGA_NEWPOP.
109
110     PGAContext *ctx;
111     int b, n;
112     :
113     b  = PGAGetBestIndex(ctx, PGA_OLDPOP);
114     n  = PGAGetPopsize(ctx) / 2;
115     if (PGADuplicate(ctx, b, PGA_OLDPOP, PGA_NEWPOP, n))
116         printf("A duplicate!\n");
117
118****************************************************************************U*/
119int PGADuplicate(PGAContext *ctx, int p, int pop1, int pop2, int n)
120{
121    int p2, fp;
122    int RetVal = PGA_FALSE;
123   
124    PGADebugEntered("PGADuplicate");
125    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGADuplicate", "p = ",
126                  PGA_INT, (void *) &p );
127    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGADuplicate", "pop1 = ",
128                  PGA_INT, (void *) &pop1 );
129    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGADuplicate", "pop2 = ",
130                  PGA_INT, (void *) &pop2 );
131    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR,"PGADuplicate", "n  = ",
132                  PGA_INT, (void *) &n );
133   
134    if (ctx->ga.NoDuplicates == PGA_TRUE) {
135        if (ctx->fops.Duplicate) {
136            fp = ((p == PGA_TEMP1) || (p == PGA_TEMP2)) ? p : p+1;
137            for (p2 = 1; p2 <= n; p2++)
138                if ((*ctx->fops.Duplicate)(&ctx, &fp, &pop1, &p2, &pop2)) {
139                    RetVal = PGA_TRUE;
140                    p2 = n+1;
141                }
142        } else {
143            for (p2 = 0; p2 < n; p2++)
144                if ((*ctx->cops.Duplicate)(ctx, p, pop1, p2, pop2)) {
145                    RetVal = PGA_TRUE;
146                    p2 = n;
147                }
148        }
149    }
150   
151    PGADebugExited("PGADuplicate");
152   
153    return(RetVal);
154}
155
156
157/*U****************************************************************************
158  PGAChange - Repeatedly apply mutation to a string (with an increasing
159  mutation rate) until one or more mutations have occurred.  This routine is
160  usually used with PGADuplicate to modify a duplicate string.  It is not
161  intended to replace PGAMutation
162
163  Category: Generation
164
165  Inputs:
166     ctx  - context variable
167     p    - string index
168     pop  - symbolic constant of the population containing string p
169
170  Outputs:
171     Mutates string p in population pop via side effect.
172
173  Example:
174     Change any string in PGA_NEWPOP that is an exact copy of a string
175     in PGA_OLDPOP.  To be complete, we should check the population again
176     if any changes are made; for simplicity, we don't.
177
178     PGAContext *ctx;
179     int b, n;
180     :
181     n  = PGAGetPopsize(ctx);
182     for (b=0; b<n; b++)
183         if (PGADuplicate(ctx, b, PGA_NEWPOP, PGA_OLDPOP, n))
184             PGAChange(ctx, b, PGA_NEWPOP);
185
186****************************************************************************U*/
187void PGAChange( PGAContext *ctx, int p, int pop )
188{
189    int    changed = PGA_FALSE;
190    int    fp, nflips;
191    double mr;
192
193    PGADebugEntered("PGAChange");
194
195    mr = ctx->ga.MutationProb;
196
197    PGADebugPrint( ctx, PGA_DEBUG_PRINTVAR, "PGAChange", " mr = ",
198                   PGA_DOUBLE, (void *) &mr );
199
200    while (( changed == PGA_FALSE ) && (mr <= 1.0)) {
201        if (ctx->fops.Mutation) {
202            fp = ((p == PGA_TEMP1) || (p == PGA_TEMP2)) ? p : p+1;
203            nflips = (*ctx->fops.Mutation)(&ctx, &fp, &pop, &mr);
204        } else {
205            nflips = (*ctx->cops.Mutation)( ctx, p, pop, mr );
206        }
207
208        if ( nflips > 0 )
209            changed = PGA_TRUE;
210        else
211            mr = 1.1*mr;
212    }
213
214    if (changed == PGA_FALSE) {
215        PGAError(ctx, "Could not change string:", PGA_WARNING, PGA_VOID, NULL);
216        PGAPrintString(ctx, stderr, p, pop);
217    }
218
219    PGADebugExited("PGAChange");
220}
221
222/*U****************************************************************************
223   PGASetNoDuplicatesFlag - A boolean flag to indicate if duplicate strings are
224   allowed in the population. Valid choices are PGA_TRUE and PGA_FALSE.  The
225   default is PGA_FALSE -- allow duplicates.
226
227   Category: Generation
228
229   Inputs:
230      ctx  - context variable
231      flag - PGA_TRUE or PGA_FALSE
232
233   Outputs:
234      None
235
236   Example:
237      Set the NoDuplicates flag to require that all strings are unique.
238
239      PGAContext *ctx;
240      :
241      PGASetNoDuplicatesFlag(ctx,PGA_TRUE);
242
243****************************************************************************U*/
244void PGASetNoDuplicatesFlag( PGAContext *ctx, int no_dup)
245{
246    PGADebugEntered("PGASetNoDuplicatesFlag");
247
248    switch (no_dup) {
249        case PGA_TRUE:
250        case PGA_FALSE:
251            ctx->ga.NoDuplicates = no_dup;
252            break;
253        default:
254            PGAError ( ctx, "PGASetNoDuplicatesFlag: Invalid value of no_dup:",
255                       PGA_FATAL, PGA_INT, (void *) &no_dup);
256            break;
257    }
258
259    PGADebugExited("PGASetNoDuplicatesFlag");
260}
261
262/*U***************************************************************************
263   PGAGetNoDuplicatesFlag - Returns PGA_TRUE if duplicates are not allowed,
264   else returns PGA_FALSE.
265
266   Category: Generation
267
268   Inputs:
269      ctx - context variable
270
271   Outputs:
272      The value of the NoDuplicates flag.
273
274   Example:
275      PGAContext *ctx;
276      int nodups;
277      :
278      nodups = PGAGetNoDuplicatesFlag(ctx);
279      switch (nodups) {
280      case PGA_TRUE:
281          printf("Duplicate strings not allowed in population\n");
282          break;
283      case PGA_FALSE:
284          printf("Duplicate strings allowed in population\n");
285          break;
286      }
287
288***************************************************************************U*/
289int PGAGetNoDuplicatesFlag (PGAContext *ctx)
290{
291    PGADebugEntered("PGAGetNoDuplicatesFlag");
292
293    PGAFailIfNotSetUp("PGAGetNoDuplicatesFlag");
294
295    PGADebugExited("PGAGetNoDuplicatesFlag");
296
297    return(ctx->ga.NoDuplicates);
298}
Note: See TracBrowser for help on using the repository browser.