comocma.hv

1 # Copyright (C) 2010 Simon Wessing 2 # TU Dortmund University 3 # 4 # This program is free software: you can redistribute it and/or modify 5 # it under the terms of the GNU General Public License as published by 6 # the Free Software Foundation, either version 3 of the License, or 7 # (at your option) any later version. 8 # 9 # This program is distributed in the hope that it will be useful, 10 # but WITHOUT ANY WARRANTY; without even the implied warranty of 11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 # GNU General Public License for more details. 13 # 14 # You should have received a copy of the GNU General Public License 15 # along with this program. If not, see <http://www.gnu.org/licenses/>. 16 17 18 __author__ = "Simon Wessing" 19 20 try: 21 xrange = range 22 except: 23 pass 24 from fractions import Fraction as Ff 25

26 -class HyperVolume:

27 """ 28 Hypervolume computation based on variant 3 of the algorithm in the paper: 29 C. M. Fonseca, L. Paquete, and M. Lopez-Ibanez. An improved dimension-sweep 30 algorithm for the hypervolume indicator. In IEEE Congress on Evolutionary 31 Computation, pages 1157-1163, Vancouver, Canada, July 2006. 32 33 Minimization is implicitly assumed here! 34 35 """ 36

37 - def __init__(self, referencePoint):

38 """Constructor.""" 39 self.referencePoint = referencePoint 40 self.list = []

41 42

43 - def compute(self, front):

44 """Returns the hypervolume that is dominated by a non-dominated front. 45 46 Before the HV computation, front and reference point are translated, so 47 that the reference point is [0, ..., 0]. 48 49 """ 50 51 def weaklyDominates(point, other): 52 for i in xrange(len(point)): 53 if point[i] > other[i]: 54 return False 55 return True

56 57 relevantPoints = [] 58 referencePoint = self.referencePoint 59 dimensions = len(referencePoint) 60 for point in front: 61 # only consider points that dominate the reference point 62 if weaklyDominates(point, referencePoint): 63 relevantPoints.append(point) 64 if any(referencePoint): 65 # shift points so that referencePoint == [0, ..., 0] 66 # this way the reference point doesn't have to be explicitly used 67 # in the HV computation 68 for j in xrange(len(relevantPoints)): 69 relevantPoints[j] = [Ff(relevantPoints[j][i]) - Ff(referencePoint[i]) for i in xrange(dimensions)] 70 self.preProcess(relevantPoints) 71 bounds = [-Ff(1.0e308)] * dimensions 72 hyperVolume = self.hvRecursive(dimensions - 1, len(relevantPoints), bounds) 73 return hyperVolume

74 75

76 - def hvRecursive(self, dimIndex, length, bounds):

77 """Recursive call to hypervolume calculation. 78 79 In contrast to the paper, the code assumes that the reference point 80 is [0, ..., 0]. This allows the avoidance of a few operations. 81 82 """ 83 hvol = Ff(0.0) 84 sentinel = self.list.sentinel 85 if length == 0: 86 return hvol 87 elif dimIndex == 0: 88 # special case: only one dimension 89 # why using hypervolume at all? 90 return -sentinel.next[0].cargo[0] 91 elif dimIndex == 1: 92 # special case: two dimensions, end recursion 93 q = sentinel.next[1] 94 h = Ff(q.cargo[0]) 95 p = q.next[1] 96 while p is not sentinel: 97 pCargo = p.cargo 98 hvol += h * (Ff(q.cargo[1]) - Ff(pCargo[1])) 99 if Ff(pCargo[0]) < h: 100 h = Ff(pCargo[0]) 101 q = p 102 p = q.next[1] 103 hvol += h * Ff(q.cargo[1]) 104 return hvol 105 else: 106 remove = self.list.remove 107 reinsert = self.list.reinsert 108 hvRecursive = self.hvRecursive 109 p = sentinel 110 q = p.prev[dimIndex] 111 while q.cargo != None: 112 if q.ignore < dimIndex: 113 q.ignore = 0 114 q = q.prev[dimIndex] 115 q = p.prev[dimIndex] 116 while length > 1 and (q.cargo[dimIndex] > bounds[dimIndex] or q.prev[dimIndex].cargo[dimIndex] >= bounds[dimIndex]): 117 p = q 118 remove(p, dimIndex, bounds) 119 q = p.prev[dimIndex] 120 length -= 1 121 qArea = q.area 122 qCargo = q.cargo 123 qPrevDimIndex = q.prev[dimIndex] 124 if length > 1: 125 hvol = Ff(qPrevDimIndex.volume[dimIndex]) + Ff( 126 qPrevDimIndex.area[dimIndex]) * (Ff(qCargo[dimIndex]) - Ff(qPrevDimIndex.cargo[dimIndex])) 127 else: 128 qArea[0] = Ff(1) 129 qArea[1:dimIndex+1] = [Ff(qArea[i]) * Ff(-qCargo[i]) for i in xrange(dimIndex)] 130 q.volume[dimIndex] = hvol 131 if q.ignore >= dimIndex: 132 qArea[dimIndex] = qPrevDimIndex.area[dimIndex] 133 else: 134 qArea[dimIndex] = hvRecursive(dimIndex - 1, length, bounds) 135 if qArea[dimIndex] <= qPrevDimIndex.area[dimIndex]: 136 q.ignore = dimIndex 137 while p is not sentinel: 138 pCargoDimIndex = Ff(p.cargo[dimIndex]) 139 hvol += Ff(q.area[dimIndex]) * Ff((pCargoDimIndex - Ff(q.cargo[dimIndex]))) 140 bounds[dimIndex] = pCargoDimIndex 141 reinsert(p, dimIndex, bounds) 142 length += 1 143 q = p 144 p = p.next[dimIndex] 145 q.volume[dimIndex] = hvol 146 if q.ignore >= dimIndex: 147 q.area[dimIndex] = Ff(q.prev[dimIndex].area[dimIndex]) 148 else: 149 q.area[dimIndex] = hvRecursive(dimIndex - 1, length, bounds) 150 if Ff(q.area[dimIndex]) <= Ff(q.prev[dimIndex].area[dimIndex]): 151 q.ignore = dimIndex 152 hvol -= Ff(q.area[dimIndex]) * Ff(q.cargo[dimIndex]) 153 return hvol

154 155

156 - def preProcess(self, front):

157 """Sets up the list data structure needed for calculation.""" 158 dimensions = len(self.referencePoint) 159 nodeList = MultiList(dimensions) 160 nodes = [MultiList.Node(dimensions, point) for point in front] 161 for i in xrange(dimensions): 162 self.sortByDimension(nodes, i) 163 nodeList.extend(nodes, i) 164 self.list = nodeList

165 166

167 - def sortByDimension(self, nodes, i):

168 """Sorts the list of nodes by the i-th value of the contained points.""" 169 # build a list of tuples of (point[i], node) 170 decorated = [(node.cargo[i], node) for node in nodes] 171 #Cheikh : comment below and write a non-buggy sorting for decorated: 172 173 ## sort by this value 174 #decorated.sort() 175 176 decorated.sort(key = lambda u: u[0]) 177 178 # write back to original list 179 nodes[:] = [node for (_, node) in decorated]

180 181 182

183 -class MultiList:

184 """A special data structure needed by FonsecaHyperVolume. 185 186 It consists of several doubly linked lists that share common nodes. So, 187 every node has multiple predecessors and successors, one in every list. 188 189 """ 190

191 - class Node:

192

193 - def __init__(self, numberLists, cargo=None):

194 self.cargo = cargo 195 self.next = [None] * numberLists 196 self.prev = [None] * numberLists 197 self.ignore = 0 198 self.area = [Ff(0.0)] * numberLists 199 self.volume = [Ff(0.0)] * numberLists 200

201 - def __str__(self):

202 return str(self.cargo) 203 204

205 - def __init__(self, numberLists):

206 """Constructor. 207 208 Builds 'numberLists' doubly linked lists. 209 210 """ 211 self.numberLists = numberLists 212 self.sentinel = MultiList.Node(numberLists) 213 self.sentinel.next = [self.sentinel] * numberLists 214 self.sentinel.prev = [self.sentinel] * numberLists 215 216

217 - def __str__(self):

218 strings = [] 219 for i in xrange(self.numberLists): 220 currentList = [] 221 node = self.sentinel.next[i] 222 while node != self.sentinel: 223 currentList.append(str(node)) 224 node = node.next[i] 225 strings.append(str(currentList)) 226 stringRepr = "" 227 for string in strings: 228 stringRepr += string + "\n" 229 return stringRepr

230 231

232 - def __len__(self):

233 """Returns the number of lists that are included in this MultiList.""" 234 return self.numberLists

235 236

237 - def getLength(self, i):

238 """Returns the length of the i-th list.""" 239 length = 0 240 sentinel = self.sentinel 241 node = sentinel.next[i] 242 while node != sentinel: 243 length += 1 244 node = node.next[i] 245 return length

246 247

248 - def append(self, node, index):

249 """Appends a node to the end of the list at the given index.""" 250 lastButOne = self.sentinel.prev[index] 251 node.next[index] = self.sentinel 252 node.prev[index] = lastButOne 253 # set the last element as the new one 254 self.sentinel.prev[index] = node 255 lastButOne.next[index] = node

256 257

258 - def extend(self, nodes, index):

259 """Extends the list at the given index with the nodes.""" 260 sentinel = self.sentinel 261 for node in nodes: 262 lastButOne = sentinel.prev[index] 263 node.next[index] = sentinel 264 node.prev[index] = lastButOne 265 # set the last element as the new one 266 sentinel.prev[index] = node 267 lastButOne.next[index] = node

268 269

270 - def remove(self, node, index, bounds):

271 """Removes and returns 'node' from all lists in [0, 'index'[.""" 272 for i in xrange(index): 273 predecessor = node.prev[i] 274 successor = node.next[i] 275 predecessor.next[i] = successor 276 successor.prev[i] = predecessor 277 if bounds[i] > node.cargo[i]: 278 bounds[i] = Ff(node.cargo[i]) 279 return node 280 281

282 - def reinsert(self, node, index, bounds):

283 """ 284 Inserts 'node' at the position it had in all lists in [0, 'index'[ 285 before it was removed. This method assumes that the next and previous 286 nodes of the node that is reinserted are in the list. 287 288 """ 289 for i in xrange(index): 290 node.prev[i].next[i] = node 291 node.next[i].prev[i] = node 292 if bounds[i] > node.cargo[i]: 293 bounds[i] = Ff(node.cargo[i])

294 295 296 297 if __name__ == "__main__": 298 299 # Example: 300 referencePoint = [2, 2, 2] 301 hv = HyperVolume(referencePoint) 302 front = [[1,0,1], [0,1,0]] 303 volume = hv.compute(front) 304

Source Code for Module comocma.hv