Population.java

Go to the documentation of this file.

/*
 *   DENOPTIM
 *   Copyright (C) 2021  Marco Foscato <marco.foscato@uib.no>
 * 
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU Affero General Public License as published
 *   by the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU Affero General Public License for more details.
 *
 *   You should have received a copy of the GNU Affero General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
package denoptim.ga;
 
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.logging.Level;
 
import denoptim.exception.DENOPTIMException;
import denoptim.fragspace.FragmentSpace;
import denoptim.fragspace.FragmentSpaceParameters;
import denoptim.graph.Candidate;
import denoptim.graph.DGraph;
import denoptim.programs.RunTimeParameters.ParametersType;
import denoptim.programs.denovo.GAParameters;
 
public class Population extends ArrayList<Candidate> implements Cloneable
{
    private static final long serialVersionUID = 1L;
    
    private AtomicInteger populationUpdate = new AtomicInteger();
    
    private XoverSitesAmongCandidates xoverCompatibilities;
    
    private GAParameters settings;
   
//------------------------------------------------------------------------------
 
    public Population(GAParameters settings)
    {
        super();
        this.settings = settings;
        FragmentSpaceParameters fsParams = ((FragmentSpaceParameters) 
                settings.getParameters(ParametersType.FS_PARAMS));
        if (fsParams!=null && 
                fsParams.getFragmentSpace().useAPclassBasedApproach())
        {
            xoverCompatibilities = new XoverSitesAmongCandidates();
        }
    }
    
//------------------------------------------------------------------------------
    
    @Override
    public boolean add(Candidate c)
    {
        boolean result = super.add(c);
        if (result)
            populationUpdate.getAndIncrement();
        return result;
    }
    
//------------------------------------------------------------------------------
    
    @Override
    public void add(int index, Candidate c)
    {
        super.add(index, c);
        populationUpdate.getAndIncrement();
    }
    
//------------------------------------------------------------------------------
    
    @Override
    public Candidate set(int index, Candidate c)
    {
        populationUpdate.getAndIncrement();
        return super.set(index, c);
    }
    
//------------------------------------------------------------------------------
    
    @Override
    public Candidate remove(int index)
    {
        populationUpdate.getAndIncrement();
        return super.remove(index);
    }
    
//------------------------------------------------------------------------------
    
    @Override
    public boolean remove(Object c)
    {
        boolean result = super.remove(c);
        if (result)
            populationUpdate.getAndIncrement();
        return result;
    }
    
//------------------------------------------------------------------------------
    
    @Override
    public boolean removeAll(Collection<?> c)
    {
        boolean result = super.removeAll(c);
        if (result)
            populationUpdate.getAndIncrement();
        return result;
    }
    
//------------------------------------------------------------------------------
    
    @Override
    public void clear()
    {
        populationUpdate.getAndIncrement();
        super.clear();
    }
    
//------------------------------------------------------------------------------
    
    @Override
    public boolean retainAll(Collection<?> c)
    {
        boolean result = super.retainAll(c);
        if (result)
            populationUpdate.getAndIncrement();
        return result;
    }
    
//------------------------------------------------------------------------------
    
    public int getVersionID()
    {
        return populationUpdate.get();
    }
    
//------------------------------------------------------------------------------
    
    public Population clone()
    {
        Population clone = new Population(settings);
 
        for (Candidate c : this)
        {
            clone.add(c);
        }
        
        clone.xoverCompatibilities = xoverCompatibilities.clone();
        
        return clone;
    }
    
//------------------------------------------------------------------------------    
    
    private class XoverSitesAmongCandidates
    {
        private LinkedHashMap<Candidate,
        LinkedHashMap<Candidate,List<XoverSite>>> data;
        
        public XoverSitesAmongCandidates()
        {
            data = new LinkedHashMap<Candidate,LinkedHashMap<Candidate, 
                    List<XoverSite>>>();
        }
        
        public void put(Candidate c1, Candidate c2, 
                List<XoverSite> xoversite)
        {     
            if (data.containsKey(c1))
            {
                data.get(c1).put(c2, xoversite);
            } else {
                LinkedHashMap<Candidate,List<XoverSite>> toC1 = 
                        new LinkedHashMap<Candidate,List<XoverSite>>();
                toC1.put(c2, xoversite);
                data.put(c1, toC1);
            }
            
            List<XoverSite> revPairs = 
                    new ArrayList<XoverSite>();
            for (XoverSite pair : xoversite)
            {
                XoverSite revPair = pair.createMirror();
                revPairs.add(revPair);
            }
            
            if (data.containsKey(c2))
            {
                data.get(c2).put(c1, revPairs);
            } else {
                LinkedHashMap<Candidate,List<XoverSite>> toC2 = 
                        new LinkedHashMap<Candidate,List<XoverSite>>();
                toC2.put(c1, revPairs);
                data.put(c2, toC2);
            }
        }
        
        public List<XoverSite> get(Candidate c1, Candidate c2)
        {
            if (data.containsKey(c1))
            {
                return data.get(c1).get(c2);
            } else {
                return null;
            }
        }
        
        public List<Candidate> getMembersCompatibleWith(Candidate cA)
        {
            List<Candidate> compatibleMembers = new ArrayList<Candidate>();
            if (data.keySet().contains(cA))
            {
                for (Candidate cB : data.get(cA).keySet())
                {
                    if (!data.get(cA).get(cB).isEmpty())
                    {
                        compatibleMembers.add(cB);
                    }
                }
            }
            return compatibleMembers;
        }
 
        public boolean contains(Candidate memberA, Candidate memberB)
        {            
            return data.keySet().contains(memberA) &&
                    data.get(memberA).containsKey(memberB);
        }
 
        public void remove(Candidate c)
        {
            data.remove(c);
            for (LinkedHashMap<Candidate, List<XoverSite>> m : 
                data.values())
            {
                m.remove(c);
            }
        }
        
        public XoverSitesAmongCandidates clone()
        {
            XoverSitesAmongCandidates cloned = new XoverSitesAmongCandidates();
            for (Candidate c1 : data.keySet())
            {
                LinkedHashMap<Candidate, List<XoverSite>> inner =
                        new LinkedHashMap<Candidate, List<XoverSite>>();
                for (Candidate c2 : data.get(c1).keySet())
                {
                    List<XoverSite> lst = new ArrayList<XoverSite>();
                    for (XoverSite arr : data.get(c1).get(c2))
                    {
                        lst.add(arr.clone());
                    }
                    inner.put(c2,lst);
                }
                cloned.data.put(c1, inner);
            }
            return cloned;
        }
    }
 
//------------------------------------------------------------------------------
    
    public List<Candidate> getXoverPartners(Candidate memberA,
            List<Candidate> eligibleParents, FragmentSpace fragSpace)
    {   
        DGraph gA = memberA.getGraph();
        
        // Update to make sure we cover any combination of members that has not 
        // been considered before
        for (Candidate memberB : eligibleParents)
        {
            if (memberA == memberB)
            {
                continue;
            }
            
            if (xoverCompatibilities.contains(memberA, memberB))
            {
                continue;
            }
    
            DGraph gB = memberB.getGraph();
            
            if (gA.sameAs(gB, new StringBuilder()))
                continue;
                
            try
            {
                List<XoverSite> xoverSites = GraphOperations
                        .locateCompatibleXOverPoints(gA, gB, fragSpace, 
                                settings.maxXOverableSubGraphSize);
                xoverCompatibilities.put(memberA, memberB, xoverSites);
            } catch (DENOPTIMException e)
            {
                settings.getLogger().log(Level.FINE, "Could not identify "
                        + "crossover sites between " + memberA.getName() 
                        + " and " + memberB.getName() + ".");
                e.printStackTrace();
            }
        }
        return xoverCompatibilities.getMembersCompatibleWith(memberA);
    }
 
//------------------------------------------------------------------------------
    
    public List<XoverSite> getXoverSites(Candidate parentA, Candidate parentB)
    {
        return xoverCompatibilities.get(parentA,parentB);
    }
 
//------------------------------------------------------------------------------
    
    public void trim(int populationSize)
    {
        int k = this.size();
        for (Candidate c : this.subList(settings.getPopulationSize(), k))
        {
            xoverCompatibilities.remove(c);
        }
        this.subList(settings.getPopulationSize(), k).clear();
    }
    
//------------------------------------------------------------------------------
    
    public double getMinFitness()
    {
        return getMinFitnessMember().getFitness();
    }
    
//------------------------------------------------------------------------------
    
    public Candidate getMinFitnessMember()
    {
        return this.stream()
                .min(Comparator.comparing(Candidate::getFitness))
                .orElse(null);
    }
    
//------------------------------------------------------------------------------
    
    public double getMaxFitness()
    {
        return this.stream()
                .max(Comparator.comparing(Candidate::getFitness))
                .orElse(null)
                .getFitness();
    }
 
//------------------------------------------------------------------------------
    
    public boolean isWithinPercentile(double value, double percentile)
    {
        double min = getMinFitness();
        double max = getMaxFitness();
        double threshold = (1.0 - percentile) * (max-min);
        
        if (value > (threshold+min))
            return true;
        else
            return false;
    }
    
//------------------------------------------------------------------------------
 
    public Candidate getCandidateNamed(String name)
    {
        return this.stream()
                .filter(candidate -> name.equals(candidate.getName()))
                .findAny()
                .orElse(null);
    }
    
//------------------------------------------------------------------------------
    
}