Skip to content

Commit

Permalink
most obvious bugs fixed
Browse files Browse the repository at this point in the history
  • Loading branch information
mairas committed Jan 28, 2010
1 parent f3c4dda commit 249b489
Showing 4 changed files with 172 additions and 99 deletions.
18 changes: 9 additions & 9 deletions itemplot.py
Original file line number Diff line number Diff line change
@@ -8,32 +8,32 @@
import pylab

def plot_item(item,c,text=None):
x,y,l,w = item.x,item.y,item.l,item.w
pylab.plot([x,x,x+l,x+l,x],[y,y+w,y+w,y,y],c)
x,y,w,h = item.x,item.y,item.w,item.h
pylab.plot([x,x,x+w,x+w,x],[y,y+h,y+h,y,y],c)
if text!=None:
pylab.text(x+l/2,y,str(l), fontsize=8,
pylab.text(x+w/2,y,str(w), fontsize=8,
horizontalalignment='center',
verticalalignment='bottom',)
pylab.text(x+l,y+w/2,str(w), fontsize=8,
pylab.text(x+w,y+h/2,str(h), fontsize=8,
horizontalalignment='right',
verticalalignment='center',)
if w>l:
pylab.text(x+l/3, y+w/2,text, fontsize=8,
if h>w:
pylab.text(x+w/3, y+h/2,text, fontsize=8,
horizontalalignment='center',
verticalalignment='center',
rotation=90)
else:
pylab.text(x+l/2, y+w*2./3,text, fontsize=8,
pylab.text(x+w/2, y+h*2./3,text, fontsize=8,
horizontalalignment='center',
verticalalignment='center',)

def plot_layout(items,L,W,show=False,draw=False):
def plot_layout(items,W,H,show=False,draw=False):
colors = ['r','g','b','c','m','y','k']
if len(items)>0:
pylab.clf()
pylab.axes(aspect='equal')
# plot the board borders
pylab.plot([0,0,0+L,0+L,0],[0,0+W,0+W,0,0],'k')
pylab.plot([0,0,0+W,0+W,0],[0,0+H,0+H,0,0],'k')

for i,item in enumerate(items):
plot_item(item,colors[i%len(colors)])
22 changes: 11 additions & 11 deletions optimize_cuts_ga.py
Original file line number Diff line number Diff line change
@@ -31,8 +31,8 @@ def input_items(filename):
items = []

for line in lines:
l,w,n,r,s = line
typ = optalg.ItemType(l, w, s, r)
w,h,n,r,s = line
typ = optalg.ItemType(w, h, s, r)
for i in range(n):
items.append(optalg.Item(typ))

@@ -48,13 +48,13 @@ def types(items):

def add_trim(items,trim):
for typ in types(items):
typ.h += trim
typ.w += trim
typ.h += trim

def remove_trim(items,trim):
for typ in types(items):
typ.w -= trim
typ.l -= trim
typ.h -= trim

if __name__=='__main__':
parser = OptionParser()
@@ -63,25 +63,25 @@ def remove_trim(items,trim):
# help="the output file name")
parser.add_option("-t","--trim",dest="trim",type="int",
help="the trim amount", default=0.)
parser.add_option("-W","--width",dest="width",type="int",
help="the plate width")
parser.add_option("-H","--height",dest="height",type="int",
help="the plate height")

(options,args) = parser.parse_args()
W = options.width
H = options.height
trim = options.trim

items = input_items(args[0])

add_trim(items,trim)

L,items = optalg.optimize(items,W+trim,verbose=True)
W,items = optalg.optimize(items,H+trim,verbose=True)

# remove the trim from the pieces
L -= trim
W -= trim
remove_trim(items,trim)

plot_layout(items,L,W,show=True)
plot_layout(items,W,H,show=True)

for item in items:
print item.l,item.w,item.x,item.y
print item.w,item.h,item.x,item.y

135 changes: 64 additions & 71 deletions striped_ga.py
Original file line number Diff line number Diff line change
@@ -83,12 +83,6 @@ def area(self):
def covered_area(self):
return self.area()

def update_strip_space(self,W,H):
"""
Nothing to update for an Item
"""
return W,H

def overlaps(self,other):
"""
Return true if the items overlap
@@ -111,20 +105,22 @@ class Strip(list):
min_item_height = 0
min_item_width = 0

def __init__(self,w=None,h=None,W=None,H=None,list_=[]):
def __init__(self,w=None,h=None,W=None,H=None,x=None,y=None,list_=[]):
super(Strip,self).__init__()
self.w = w
self.h = h
self.W = W
self.H = H
self.x = x
self.y = y
self += list_

def __repr__(self):
r = [repr(p) for p in self]
s = ",\n".join(r)
s_i = "[\n" + indent(s,2) + "\n]"
return "%s(%r,%r,%r,%r,%s)" % \
(type(self).__name__,self.w,self.h,self.W,self.H,s_i)
return "%s(%r,%r,%r,%r,%r,%r,%s)" % \
(type(self).__name__,self.w,self.h,self.W,self.H,self.x,self.y,s_i)


# note: this is a class method!
@@ -190,23 +186,27 @@ def fits(self,item):


def populate(self,items):
"""
place all items in the strip
removes elements from the items list
"""
# first populate substrips
for item in self:
if not isinstance(item,Item):
item.populate(items)
for item in items[:]:
# available width and height
av_height = self.H-self.h
av_width = self.W-self.w
if item.h<av_height and item.w<av_width:
self.place(items,item,av_height,av_width)
av_width,av_height = self.get_available_space()
if item.h<=av_height and item.w<=av_width:
self.place(items,item)
elif item.type.rotatable:
item.rotate()
if item.h<av_height and item.w<av_width:
self.place(items,item,av_height,av_width)
self.place(items,item)

def place(self,items,item,av_height,av_width):
if av_width>self.min_item_width:
def place(self,items,item):
if self.is_wrappable(item):
s = self.ortho()
s.append(item)
self.append(s)
@@ -226,7 +226,7 @@ def remove_duplicates(self,seen):
for i in range(len(self)-1,-1,-1):
item = self[i]
if isinstance(item,Item):
if seen.has_key(item.id):
if item.id in seen:
#print "dropped in remove_duplicates:", item.id
self.pop(i)
num_removed += 1
@@ -242,38 +242,26 @@ def fix_layout(self,items,W,H):
"""
Fix the layout after crossover and mutation operations.
"""
print "here 1: # items:", len(self.get_items())
nd = self.remove_duplicates({})
self.update_dimensions(W,H)
print "here 2: # items:", len(self.get_items())

nr = self.repair()

self.update_dimensions(W,H)
print "here 3: # items:", len(self.get_items())
nd = self.remove_duplicates({})
self.update_dimensions(W,H)
print "here 4: # items:", len(self.get_items())

# get a dict of unplaced items
# get a list of unplaced items

unplaced = {}
for e in items[:]:
unplaced[e.id] = e
for e in items[:]: unplaced[e.id] = e
placed = self.get_items()
for p in placed:
try: del unplaced[p.id]
except: pass
unplaced = unplaced.values()

self.update_dimensions(W,H)
print "here 5: # items:", len(self.get_items())
nr = self.repair()
print "here 6: # items:", len(self.get_items())
self.update_dimensions(W,H)
print "here 7: # items:", len(self.get_items())
self.populate(unplaced)
print "here 8: # items:", len(self.get_items())

self.update_dimensions(W,H)
print "here 9: # items:", len(self.get_items())

assert(len(unplaced)==0)

@@ -289,12 +277,7 @@ def update_dimensions(self,W,H):
self.update_sizes()
self.update_available_space(W,H)
pairs = self.check_for_overlap()
if pairs:
print "Overlapping pairs:"
for p in pairs:
print p
print(repr(self))
assert(0)
assert(len(pairs)==0)

def update_sizes(self,x=0,y=0):
"""Update the minimum sizes required to accommodate each subitem."""
@@ -320,23 +303,6 @@ def update_sizes(self,x=0,y=0):

return w,h

def update_available_space(self,W,H):
"""
Update the space available for the item.
W: available width.
H: available height.
"""
self.H = H
self.W = W
for i,item in enumerate(self):
if i < len(self)-1:
# not the last item
W,H = item.update_strip_space(W,H)
else:
# last item
if not isinstance(item,Item):
item.update_available_space(W,H)

def repair_strip(self,i,item):
"""
Perform specific repair operations on a substrip.
@@ -426,15 +392,27 @@ def dim_inc(self,w,h,ew,eh):
w = w+ew
return w,h

def get_available_space(self):
av_width = self.W-self.w
av_height = self.H
return av_width,av_height

def update_strip_space(self,W,H):
def update_available_space(self,W,H):
"""
Update available strip space in an orientation-specific manner
Update the space available for the strip
"""
w = min(self.w,W)
self.update_available_space(w,H)
W -= w
return W,H
self.W = W
self.H = H

for i,item in enumerate(self):
if i < len(self)-1:
# not the last item in strip
w = min(item.w,W)
W -= w
else:
w = W
if not isinstance(item,Item):
item.update_available_space(w,H)

def is_wrappable(self,item):
return item.h+self.min_item_height<=self.H
@@ -460,14 +438,27 @@ def dim_inc(self,w,h,ew,eh):
w = max(w,ew)
return w,h

def update_strip_space(self,W,H):
def get_available_space(self):
av_width = self.W
av_height = self.H-self.h
return av_width,av_height

def update_available_space(self,W,H):
"""
Update available strip space in an orientation-specific manner
Update the space available for the strip
"""
h = min(self.h,H)
self.update_available_space(W,h)
H -= h
return W,H
self.W = W
self.H = H

for i,item in enumerate(self):
if i < len(self)-1:
# not the last item in strip
h = min(item.h,H)
H -= h
else:
h = H
if not isinstance(item,Item):
item.update_available_space(W,h)

def is_wrappable(self,item):
return item.w+self.min_item_width<=self.W
@@ -562,8 +553,7 @@ def mutate(self,mutation_rate):
self.repair()

def repair(self):
print repr(self.strip)
self.strip.fix_layout(self.items,self.H,self.W)
self.strip.fix_layout(self.items,self.W,self.H)
# must have all items in the layout
if len(self.strip.get_items())!=len(self.items):
print "Danger, Will Robinson!"
@@ -583,6 +573,8 @@ def asString(self):

def optimize(items,H,generations=30,verbose=False,randomize=False):
items.sort(key=lambda x: x.area(), reverse=True)
for i in items:
print repr(i)
Strip().update_item_min_dims(items)
StripChromosome.items = items
StripChromosome.H = H
@@ -599,6 +591,7 @@ def optimize(items,H,generations=30,verbose=False,randomize=False):
size=100,
crossover_rate=0.7, mutation_rate=0.2)
best = env.run()
best.strip.update_dimensions(StripChromosome.W,StripChromosome.H)
#best.strip.sort()
pickle.dump(best,open("striped_ga.pickle","w"))
output_items = best.strip.get_items()
Loading

0 comments on commit 249b489

Please sign in to comment.