# ABC.py
#
#***********************************************************
#
# Python Modul zur Optimierung von kombinatorischen Anordnungsproblemen
# mittels Artificial Bee Colony Algorithm (Bienenalgorithmus)
#
# Datum: 11.09.2015
#
# Autor : Lars Ulke-Winter  
#         BTU Cottbus-Senftenberg
#         Fachgebiet Polymerbasierter Leichtbau
#
#***********************************************************


import numpy
from random import SystemRandom
from copy import deepcopy


class Bee(object):
    """
    Implements the an Bee object for ABC-Optimization
    """
    
    def __init__(self, fitnessFunction, searchSpace, values=None, status='Scout'):
        """
        
        Arguments:
        - fitnessFunction: refered fitness or quality function
        - searchSpace: list of possible assignments for each variable
        - values: vector of current solution (default=None)
        - status: status of bee in the searching process (default='Scout', 'Employ', 'Onlooker')
        """
        self.fitnessFunction = fitnessFunction
        self.searchSpace = searchSpace
        self.values = values
        self.status = status

        self.fitness = None # Qualitaetsmass der Loesung (Quelle)
        self.neighbourhood = [] # Matrix der Nachbarschaften
        self.follow = None # fuer Onlooker Bienen
        self.exploitedStatus = None # fuer Employ Bienen


    def randomInitalizeBee(self): # Scout Bienen generieren
        """
        Initialize solution proposals randomly and sets Bee.status -> 'Scout'
        """
        self.status = 'Scout'
        self.follow = None  # Scout Bienen folgen keiner anderen
        self.exploited = None # Scout Bienen beuten die Quellen nicht aus, sondern Suchen nur zufaellig
        
        self.values = []
        for var in self.searchSpace:
            self.values.append(SystemRandom().choice(var))


    def getFitness(self):
        """
        Compute fitness value according to self.fitnessFunction and self.values
        sets attribute self.fitness
        """
        self.fitness=self.fitnessFunction(self.values)
        

    def getNeighbourhood(self,allowableFailure=10): # Employ Bienen generieren
        """
        Generate list of self.neighbourhood and sets Bee.status -> 'Employ'
        """
        self.status = 'Employ'
        self.follow = None  # Employed Bienen folgen keiner anderen
        # Zaehler self.exploitedStatus setzen: gibt an, wie oft hintereinander keine Verbesserung des Zielfunktionswertes durch die Nachbarschaftssuche der Onlooker Bienen erzeilt wurde. Bei  self.exploitedStatus == 0 --> Verwandlung in Scout Biene
        self.exploitedStatus = allowableFailure 
        # aktuelle Nachbarschaftsmatrix loeschen
        self.neighbourhood = []
        
        leftOfValues = []
        rightOfValues = []
        minIndex = 0
        for varIndex,var in enumerate(self.values):
            maxIndex = len(self.searchSpace[varIndex])-1
            # wievielte Listenelement ist diese aktuelle Belegung
            indexInSearchSpace = self.searchSpace[varIndex].index(var)
            # linken und rechten Nachbarindex merken
            leftIndex = indexInSearchSpace-1; rightIndex = indexInSearchSpace+1 
            # wenn die Bereichsgrenzen ueberschritten werden auf jeweilige Bereichsgrenze setzten
            if leftIndex < minIndex:
                leftIndex = minIndex
            if rightIndex > maxIndex:
                rightIndex = maxIndex
                
            leftOfValues.append(self.searchSpace[varIndex][leftIndex])
            rightOfValues.append(self.searchSpace[varIndex][rightIndex])
        # Nachbarschaftsmatrix erstellen
        self.neighbourhood = list((leftOfValues,self.values,rightOfValues))


    def generateOnlooker(self): # Onlooker Bienen generieren
        """
        Returns an follower Bee (onlooker) with values lie on its side neighbourhood of the refered Employed Bee
        """
        neighbourhoodValues = []
        for i,v in enumerate(self.values):
            # fuer jede Variable einen zufaelligen Nachbarwert aus der Nachbarschaftsmatrix self.neighbourhood auswaehlen
            selectedNeighbour=SystemRandom().choice([0,1,2]) # 0 --> Left, 1 --> curent, 2 --> right
            neighbourhoodValues.append(self.neighbourhood[selectedNeighbour][i])
        # Onlooker Biene erzeugen, die in der eigenen Nachbarschaft sucht
        onlooker = Bee(self.fitnessFunction, self.searchSpace, values=neighbourhoodValues, status='Onlooker')
        # Onlooker Biene folgt der aktuellen Employed Biene
        onlooker.follow = self
        return onlooker


class Hive(object):
    """
    Collect Bee-objects with same and fitnessFunction and searchSpace 
    """
    def __init__(self, bees, searchSpace=[], fitnessFunction=None, randomCreate=True, membersize=100):
        """
        Arguments:
        - `bees`: List of Bee-objects or an empty one []
        - `searchSpace`: List of List with possible symbols for each variable for whole Hive --> [[0.1, 0.2],[1,2,3,4],['a','b','c','d']], should be ordered
        - `fitnessFunction`: Fitness function which are the Bee-Objects associated with (returns a scalar for real order problem)
        - `randomCreate`: should the Bee-objects randomly create; default --> True
        - `membersize`: if randomCreate=True then create membersize Bee-objects randomly
        """
        self.bees = bees
        self.membersize=len(bees)
        self.searchSpace = searchSpace
        self.numberOfVariables = len(self.searchSpace)
        self.fitnessFunction = fitnessFunction
        self.averageFitness = None
        self.minFitness = None

        if randomCreate:
            self.membersize=membersize
            self.randomInitalizeHive(self.membersize)


    def randomInitalizeHive(self,membersize=10):
        """
        Initilize randomly an Hive with membersize Bee-objects where variables contain self.searchSpace  

        Arguments:
        - `membersize`: Number of Bee-objects to create
        """
        beeList=[]
        for j in range(membersize):
            b = Bee(self.fitnessFunction,self.searchSpace,values=None,status='Scout')
            b.randomInitalizeBee()
            beeList.append(b)
        self.bees=beeList


    def _order2Fitness(self):
        """
        Helping method
        Orders the Bee-objects of self.bees according their fitness min. fitness first
        Sets the Attributes self.maxFitness as well as self.averageFitnesses
        """
        self.bees.sort(key=lambda bee: bee.fitness)#,reverse=True)
        # sets Attribute self.maxFitness
        self.minFitness=self.bees[0].fitness
        # sets Attribute self.averageFitness
        fitnessValues = []
        for bee in self.bees:
            fitnessValues.append(bee.fitness)
        sumOfFitnesses=numpy.sum(fitnessValues)
        self.averageFitness = sumOfFitnesses/self.membersize
        

    def getAllFitnesses(self):
        '''
        Compute the fitness of all Bee-objects of self.bees, and order min. fitness First
        '''
        for bee in self.bees:
            bee.getFitness() # aufruf Bee-Objekt.getFitness()
        # Ordnen nach aufsteigender Fitness in self.bees
        self._order2Fitness()


class ABCOpt(object):
    """
    Implements the optimization strategy acoording to foraging of Artifical Bee Colonies
    """
    
    def __init__(self, startHive):
        """
        
        Arguments:
        - startHive: Hive-object to start with (fitness calculation isn't necessary)
        """
        self.hive = startHive
        self.selection = None
        self.selectionSwitch = None
        self.numberOfEmployBees = None
        self.listOfEmployBees = []
        self.followFailure = None
        self.maxNumberOfIterations = None
        self.terminationCounter = None
        self.funCalls = 0 # Funktionsaufrufe
        self.best = None
        

    def _selection(self, listForSelection, method='rouletteWheel'):
        """
        Helping method
        Roulett Wheel selection of Bee-objects in listForSelection according to their fitness
        
        Arguments:
        - `listForSelection`: in this List is selected
        - `method`: selection method ('rouletteWheel' (default),'rankBased')
        """
        # Liste der Fitnesswerte der Bee-objekte in der Liste self.listOfEmployBees bestimmt durch den Optimierungsparameter der Methode relPortionOfEmployBees der Methode getBest(...)
        fitnessList = []
        for b in listForSelection:
            fitnessList.append(b.fitness)
        fitnessList = numpy.array(fitnessList) # in fitnessList in numpy array umwandeln
        # Auswahlwahrscheinlichkeitsvektor probList aufbauen; hoechste Wahrscheinlichkeit letztes Elemement d.h. Element mit hoechster Fitness
        if method=='rankBased':
            listOfRanks = numpy.array(range(1,len(fitnessList)+1))
            cumFit = numpy.sum(listOfRanks)
            probList = 1./cumFit*numpy.array(listOfRanks)
        else: # normale Roulette Wheel selektion
            cumFit = numpy.sum(fitnessList)
            probList = 1/cumFit*fitnessList

        # gleichverteilte Zufallszahl erzeugen [0,1)
        randNumber = SystemRandom().random()
        # Aufsummierte Wahrscheinlichkeiten
        preCumProb=0.; cumProb=0.
        # herausfinden in welchem zugeordneten Bereich die Zufallszahl gezogen wurde
        for index,value in enumerate(probList):
            cumProb+=value
            if (cumProb < randNumber) and (preCumProb < randNumber):
                preCumProb += value
            else:
                break
        # Rueckgabe des gezogenene Individuums
        return listForSelection[index]


    def getBest(self, selection='rouletteWheel', selectionSwitch = 40,
                relPortionOfEmployBees=0.5, followFailure=10,
                maxNumberOfIterations=100, terminationCounter = 30,
                showIteration='YES'):
        """
        Returns Tuple of: best individual an (Bee-object), number of iterations (Integer), number of function calls (Integer)
        
        Arguments:
        - `selection`: Onlooker Bees (follower) use this selection process for their Employ Bees (default='rouletteWheel' also possible 'rankBased')
        - `selectionSwitch`: After iteration selectionSwitch the selection process for their Employ Bees is 'rankBased'
        - `relPortionOfEmployBees`: Relativ portion of Employ Bees during the optimization (default=0.5)
        - `followFailure`: after How many tries of failed Onlooker Bee searches the related Employ Bee become an Scout Bee (exploited value) (default=10)
        - `maxNumberOfIterations`: Maximum number of iterations (default=100)
        - `terminationCounter`: Maximum number of iterations without improvement of overall fitness value best.fitness
        """
        # Optimierungsparameter setzen
        self.selection = selection
        self.selectionSwitch = selectionSwitch

        self.numberOfEmployBees = int(self.hive.membersize*relPortionOfEmployBees)
        self.followFailure = followFailure
        self.maxNumberOfIterations = maxNumberOfIterations
        self.terminationCounter = terminationCounter

        # Berechnen und ordnen der Startpopulation, aktuell alles Scout-Bienen
        self.hive.getAllFitnesses()
        self.funCalls += self.hive.membersize
        # das derzeit Beste individuum behalten (Simple Elitism)
        self.best = deepcopy(self.hive.bees[-1])

        iteration = 0
        while (iteration < self.maxNumberOfIterations) and (self.terminationCounter > 0):
            # self.terminationCounter verringern (wird bei einer globalen Verbesserung des Zielfunktionswertes zurueckgesetzt)
            self.terminationCounter -= 1
            # Counter der ab selectionSwitch auf 'RankBased' Selection umschaltet um eins verringern
            self.selectionSwitch -= 1
            # Auswahl der self.numberOfEmployBees Besten Individuen von denen follower Bienen abgeleitet werden koennen (fuehren Schwaenzeltanz in Form einer Wahrscheinlichkeitsauswahl durch)
            listOfEmployBees = deepcopy(self.hive.bees[-self.numberOfEmployBees:])
            # die ausgewaehlten self.numberOfEmployBees Bienen die derzeitig noch keinen Employ status besitzen in Employ umwandeln, Nachbarschaftsumgebung zuweisen zu der abgeleitete (Onlookers) fliegen koennen
            # Employ Bienen die noch nicht erschoepft sind bleiben erhalten, damit entspricht einer Iteration einem Durchlauf von Onlooker Bienen
            for b in listOfEmployBees:
                if b.status != 'Employed':
                    b.getNeighbourhood(allowableFailure=followFailure) # aktuelle Nachbarschaftsumgebung berechnen und maximal moeglicher allowableFailure Wert bis zum Scout Status festlegen

            self.hive.bees = [] # Liste der Bienen im Hive loeschen
            # Hive wieder auffuellen
            for i in range(self.hive.membersize):
                # wenn Counter iteration selectionSwitch mal durchgelaufen ist, auf 'rankBased' selection umschalten
                if self.selectionSwitch < 0:
                    onlook = self._selection(listOfEmployBees, method='rankBased').generateOnlooker() # Auswahl der Employ Biene, welche eine Onlooker Biene (Follower) erzeugt
                else: # sonst Employ Auswahl nach method=selection
                    onlook = self._selection(listOfEmployBees, method=selection).generateOnlooker() # Auswahl der Employ Biene, welche eine Onlooker Biene (Follower) erzeugt 
                onlook.getFitness(); self.funCalls += 1
                # Vergleich der Zielfunktionswerte von Onlooker Biene mit der zugehoerigen Employ Biene, und behalten der jeweils Besten (greedy selection des Individuums mit hoeherem Funktionswertes)
                if onlook.fitness <= onlook.follow.fitness: # wenn keine Verbesserter Zielfunktionwert gefunden wurde
                    onlook.follow.exploitedStatus -= 1 # Verringere den Ausbeutungsstatus der Quelle
                    self.hive.bees.append(onlook.follow) # und behalte die Employ Biene (Quelle)
                else:
                    self.hive.bees.append(onlook) # ansonsten behalte den Onlooker Follower
            # Inidividuen Aufsteigend Sortieren
            self.hive._order2Fitness()
            # das derzeit Beste individuum behalten (Simple Elitism)
            if self.best.fitness < self.hive.bees[-1].fitness:
                self.best = deepcopy(self.hive.bees[-1])
                # self.terminationCounter zuruecksetzen d.h. erneut terminationCounter iterationen ohne Verbesserung zulassen
                self.terminationCounter = terminationCounter

            # heraussuchen der Bienen deren Quellen ausgebeutet wurden (die ohne Verbesserung des Zielfunktionswertes mehr als followFailure angeflogen wurden)
            exploitedEmploys = filter(lambda b: (b.status=='Employ') and (b.exploitedStatus < 0), self.hive.bees)
            # sowie die Restlichen Bienen
            onlookersAndEmploys = filter(lambda b: not((b.status=='Employ') and (b.exploitedStatus < 0)), self.hive.bees)
            # entsprechend der ausgebeuteten Quellen, neue Scout Bienen erzeugen
            newScoutList = []
            for i in range(len(exploitedEmploys)):
                newScoutBee = Bee(self.hive.fitnessFunction, self.hive.searchSpace, values=None, status='Scout')
                newScoutBee.randomInitalizeBee()
                newScoutBee.getFitness(); self.funCalls += 1
                newScoutList.append(newScoutBee)
            # Scout Bienen an aktuelle Liste der Restlichen Bienen anhaengen
            self.hive.bees = onlookersAndEmploys + newScoutList
            # Inidividuen Aufsteigend Sortieren, zusaetzlich wird die durchschnittliche Fitness (self.hive.averageFitness) neu berechnet
            self.hive._order2Fitness()
            
            if showIteration=='YES':
                relScouts = float(len(newScoutList))/self.hive.membersize # relativer Anteil an Scout Bienen, d.h. zufallsbasierten Loesungen wenn die Quelle nach followFailure Versuchen erschoepft war
                onlookers = filter(lambda b: b.status=='Onlooker', self.hive.bees)
                relOnlookers = float(len(onlookers))/self.hive.membersize # relativer Anteil an Onlooker Bienen d.h. der Verbesserungen in der jeweiligen Nachbarschaft
                empl = filter(lambda b: b.status=='Employ', self.hive.bees)
                relEmploys = 1.-(relScouts+relOnlookers) # relativer Anteil bei dem in der Nachbarschaft keine Verbesserung eingetreten ist (Employs)
                print 'Iteration: %d;  Best Fitness: %.2f;  Aver. Fitness: %.2f | Distribution of Bees: Employs %.3f, Onlookers %.3f, Scouts %.3f'\
                      %(iteration,self.best.fitness,self.hive.averageFitness,relEmploys,relOnlookers,relScouts)

            # naechste Iteration
            iteration += 1
        # Rueckgabe des Tuples: Bestes Bee-Object (max Fitness), Iterationen, benoetigte Funktionsaufrufe
        return self.best, iteration, self.funCalls
        

# Test
if __name__ == '__main__':

    # Fitnessfunktion
    def f(x):
        '''
        Returns the sum of components in vector x
        '''
        return numpy.sum(x)

    # Possible variable assignments should be ordered, otherwise it becomes pure random search
    # (sub vector length must not necessarily be the same size)
    space = [
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [10., 9., 8., 7., 6., 5., 4., 3., 2., 1.],
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [10., 9., 8., 7., 6., 5., 4., 3., 2., 1.],
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [10., 9., 8., 7., 6., 5., 4., 3., 2., 1.],
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [10., 9., 8., 7., 6., 5., 4., 3., 2., 1.],
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [10., 9., 8., 7., 6., 5., 4., 3., 2., 1.],
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.],
             [10., 9., 8., 7., 6., 5., 4., 3., 2., 1.],
             ] # maximale Summe = 150 -->10^15 Moeglichkeiten

    ## spaceUnordered = [
    ##          [2.,  7., 3., 5., 9., 6., 4., 8., 1., 10.],
    ##          [3., 9., 4., 7., 2., 5., 10., 6.,8., 1.],
    ##          [9., 4., 3., 1., 10., 5., 7., 8., 2., 6.],
    ##          [10., 2., 8., 7., 1., 3., 4., 5., 9., 6.],
    ##          [8., 1., 9., 4., 7., 6., 2., 10., 3., 5.],
    ##          [10., 3., 8., 7., 1., 5., 2., 9., 4., 6.],
    ##          [1., 9., 3., 8., 5., 10., 7., 4., 2., 6.],
    ##          [1., 10., 8., 4., 5., 9., 7., 3., 6., 2.],
    ##          [4., 2., 5., 7., 1., 8., 10., 3., 9., 6.],
    ##          [9., 7., 3., 1., 5., 6., 2., 8., 4., 10.],
    ##          [3., 2., 6., 4., 9., 1., 10., 8., 5., 7.],
    ##          [5., 6., 1., 7., 10., 9., 4., 3., 8., 2.],
    ##          [1., 7., 6., 9., 5., 3., 2., 8., 4., 10.],
    ##          [10., 2., 5., 7., 3., 6., 4., 8., 1., 9.],
    ##          [7., 4., 1., 10., 6., 3., 9., 5., 2., 8.],
    ##          ] # maximale Summe = 150 -->10^15 Moeglichkeiten

    print '# ABCOpt Test #'
    print
    h2 = Hive([], searchSpace=space, fitnessFunction=f, randomCreate=True, membersize=150)
    abc1=ABCOpt(startHive=h2)
    # start Optimization (find maximum of f(x))
    best, iteration, funCalls = abc1.getBest(selection='rouletteWheel',
                                             selectionSwitch=20,
                                             relPortionOfEmployBees=0.5,
                                             followFailure=20,
                                             maxNumberOfIterations=100,
                                             showIteration='YES')
    
    print '############################'
    print 'Solution after '+str(iteration)+' iterations'
    print '############################'
    print str(best.values)+' fitness: '+str(best.fitness)+'  required function calls '+str(funCalls) 

    ###