/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.apache.commons.math3.genetics; import org.apache.commons.math3.exception.DimensionMismatchException; import org.apache.commons.math3.exception.MathIllegalArgumentException; import org.apache.commons.math3.exception.util.LocalizedFormats; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.List; /** * Random Key chromosome is used for permutation representation. It is a vector of a fixed length of * real numbers in [0,1] interval. The index of the i-th smallest value in the vector represents an * i-th member of the permutation. * *
For example, the random key [0.2, 0.3, 0.8, 0.1] corresponds to the permutation of indices * (3,0,1,2). If the original (unpermuted) sequence would be (a,b,c,d), this would mean the sequence * (d,a,b,c). * *
With this representation, common operators like n-point crossover can be used, because any * such chromosome represents a valid permutation. * *
Since the chromosome (and thus its arrayRepresentation) is immutable, the array representation * is sorted only once in the constructor. * *
For details, see: * *
representation
can not represent
* a valid chromosome
*/
public RandomKey(final Listrepresentation
can not represent
* a valid chromosome
*/
public RandomKey(final Double[] representation) throws InvalidRepresentationException {
this(Arrays.asList(representation));
}
/** {@inheritDoc} */
public Listrepresentation
and returns a (generic) list
* with the permuted values.
*
* @param representation
* @return list with the sequence values permuted according to the representation
* @throws DimensionMismatchException iff the length of the sequence
,
* representation
or sortedRepr
lists are not equal
*/
private static true
iff another
is a RandomKey and encodes the same
* permutation.
*
* @param another chromosome to compare
* @return true iff chromosomes encode the same permutation
*/
@Override
protected boolean isSame(final Chromosome another) {
// type check
if (!(another instanceof RandomKey>)) {
return false;
}
RandomKey> anotherRk = (RandomKey>) another;
// size check
if (getLength() != anotherRk.getLength()) {
return false;
}
// two different representations can still encode the same permutation
// the ordering is what counts
Listdata
sorted by
* comparator
. The data
is not modified during the process.
*
* This is useful if you want to inject some permutations to the initial population.
*
* @param This method can be viewed as an inverse to {@link #decode(List)}.
*
* @param type of the data
* @param data list of data determining the order
* @param comparator how the data will be compared
* @return list representation of the permutation corresponding to the parameters
*/
public static List data, final Comparator comparator) {
List sortedData = new ArrayList(data);
Collections.sort(sortedData, comparator);
return inducedPermutation(data, sortedData);
}
/**
* Generates a representation of a permutation corresponding to a permutation which yields
* permutedData
when applied to originalData
.
*
* type of the data
* @param originalData the original, unpermuted data
* @param permutedData the data, somehow permuted
* @return representation of a permutation corresponding to the permutation
* originalData -> permutedData
* @throws DimensionMismatchException iff the length of originalData
and
* permutedData
lists are not equal
* @throws MathIllegalArgumentException iff the permutedData
and originalData
*
lists contain different data
*/
public static List originalData, final List permutedData)
throws DimensionMismatchException, MathIllegalArgumentException {
if (originalData.size() != permutedData.size()) {
throw new DimensionMismatchException(permutedData.size(), originalData.size());
}
int l = originalData.size();
List origDataCopy = new ArrayList(originalData);
Double[] res = new Double[l];
for (int i = 0; i < l; i++) {
int index = origDataCopy.indexOf(permutedData.get(i));
if (index == -1) {
throw new MathIllegalArgumentException(
LocalizedFormats.DIFFERENT_ORIG_AND_PERMUTED_DATA);
}
res[index] = (double) i / l;
origDataCopy.set(index, null);
}
return Arrays.asList(res);
}
/** {@inheritDoc} */
@Override
public String toString() {
return String.format("(f=%s pi=(%s))", getFitness(), baseSeqPermutation);
}
/**
* Helper for constructor. Generates a list of natural numbers (0,1,...,l-1).
*
* @param l length of list to generate
* @return list of integers from 0 to l-1
*/
private static List