Digital Signal Processing Reference
In-Depth Information
of a chromosome was long, it took a lot of time to examine the chromosome for-
mat. Consequently, it wasted enormous computation time to renew a chromosome.
Therefore, this chapter introduces a new method for the crossover which does not
waste time to renew a chromosome. However, the introduced method must be per-
formed only when the parent chromosomes are already in the CSD format. Then,
the offspring will be permanently maintained in the CSD format. The CSD-based
crossover is introduced as follows.
1. If
C
P
N
1
&
C
P
N
1
−
1
=
1 then
C
P
N
1
−
1
=
C
P
N
1
−
1
.
2. If
C
P
N
2
&
C
P
N
2
+
1
=
1 then
C
P
N
2
=
C
P
N
2
.
3. If
C
P
N
1
&
C
P
N
1
−
1
=
1 then
C
P
N
1
−
1
=
C
P
N
1
−
1
.
4. If
C
P
N
2
&
C
P
N
2
+
1
=
C
P
N
2
.
5. Proceed to the crossover process of the two points
P
1
and
P
2
with
N
1
and
N
2
.
The notations
C
P
N
i
,
i
1 then
C
P
N
2
=
1
,
2, represent the
N
i
th bit of the
P
i
th chromosome, and
C
represents the complement number of
C
. The symbol “&” represents the logical
and
operation.
=
11.3.3 CSD-Based Mutation
A mutation for a binary coded chromosome always simply changes 0 to 1, or vice
versa. However, for a CSD structure, a mutation will destroy the CSD format. In
this chapter, we introduce a method for the mutation so that the CSD format is
maintained after mutation.
The CSD structure will be affected only when a mutation for a bit from 0 to 1
occurs. The CSD structure is not affected by the transform for a bit from 1 to 0. That
is, the CSD structure might be destroyed only when the new value of the mutation
point is 1. Consequently, for retaining the CSD format, we may only focus on the
bit of mutation and its two neighbor bits. Based on this idea, the following steps are
performed for the CSD-based mutation.
Step 1: Inspect the value of the point of mutation. As mentioned before, if the value
of the bit selected for mutation is '1', the structure will not be influenced after
mutation. Nothing should be done except for mutation. However, if it is '0', the
mutation will transform the bit from '0' to '1' and hence may destroy the CSD
structure.
Step 2: Examine the value of the bits adjacent to the mutation bit. If the value of
any of them is '1', suitable changes are required. If the values are both '0', we
don't need to change them.
Step 3: If any change is necessary in Step 2, find the last significant bit in a series
of '1's and change it to zero. Repeat this step until the CSD format is retained.
Search WWH ::
Custom Search