Michael von Aichberger <[EMAIL PROTECTED]> wrote:
> Imagine you had a given length. Like:
>
> length = 315
>
> And you needed to cover that length with smaller pieces. You had a set of
> pieces of a given length, like for instance:
>
> piecesL = [13, 27, 35, 48, 90, 111, ...]
>
>
> Now the algorithm I am looking for should chose any number of the pieces in
> piecesL and add them up the the given length. The pieces can be used several
> times. If the full length cannot be achieved because of the given values,
> the one solution should be found that comes closest.
>
> So I need a solution in the style of
>
> solutionL = [13, 13, 13, 27, 90, 90, ...]
Hi Michael,
Here are a couple of solutions to the particular problem that you give:
[27, 27, 27, 27, 27, 90, 90]
[27, 27, 27, 48, 48, 48, 90]
Your problem lends itself nicely to a genetic algorihtm, where a number of
near solutions are created then combined to produce even nearer solutions.
Below you will find my full genetic algorithm. Here is the output from my
message window for my tests, where the solution should add up to 16 and the
list of lengths are the first nine prime numbers:
genePool = script("Genetics").new()
put genePool.mFindSolution(16, [2, 3, 5, 7, 11, 13, 17, 19, 23])
-- [[2, 2, 2, 5, 5], [2, 7, 7], [3, 13], [2, 3, 3, 3, 5]]
-- [[3, 13], [3, 3, 3, 7], [2, 7, 7]]
-- [[3, 13], [2, 7, 7], [5, 11], [2, 3, 11]]
-- [[3, 13], [2, 3, 11]]
Note that running the algorithm four times gave four different sets of
correct answers. Genetic algorithms do not guarantee a correct answer.
What they do provide is a shortcut to an answer that is close enough.
My script is very arbitrary in places, and there are many ways in which it
could be optimized. You may want to include other criteria for fitness,
such as how many numbers need to be summed together.
Have fun,
James
----------------------------------------------------------------------------
-- PARENT SCRIPT "Genetics
----------------------------------------------------------------------------
-- GENETICS --
--
-- February 2002, James Newton, [EMAIL PROTECTED]
--
-- An example of a genetic algorithm which can be used to find which
-- numbers in a given list can be added together to create a given
-- number. Numbers in the list may be used more than once.
--
-- Examples:
-- genePool = script("Genetics").new()
-- put genePool.mFindSolution(16, [2, 3, 5, 7, 11, 13, 17, 19, 23])
-- -- [[5, 11]]
-- -- [[3, 13], [5, 11]]
-- -- [[3, 13], [2, 7, 7], [2, 2, 5, 7]]
-- -- [[3, 13], [3, 3, 3, 7], [5, 11]]
-- PROPERTY DECLARATIONS --
property pList -- list of numbers which can be used for the sum
property pCount -- number of items in pList
property pNumber -- number which must be created from a sum of the
-- numbers in pList
-- PUBLIC METHODS --
on new(me, aList)
-- Ensure that there is a list of items to choose from (the list may
-- be empty)
pList = []
me.mMerge(aList, pList)
return me
end new
on mFindSolution(me, aNumber, aNumberSource) -------------------------
-- SENT from a different script
-- INPUT: <aNumber> should be a floating point or integer number
-- <aNumberSource> should a list of numbers, in which case
-- it will replace the current pList
-- RETURNS: a list with the combination of numbers in pList which,
-- when added, reach the closest to <aNumber>
--------------------------------------------------------------------
if listp(aNumberSource) then
-- Use the numbers in aNumberSource instead of pList
tList = []
me.mMerge(aNumberSource, tList)
if tList.count then
pList = tList
end if
end if
-- Look for an exact match
if pList.getPos(aNumber) then
-- Only one number is required
return [aNumber]
else
-- Generate a gene pool of possible solutions then pick the best.
-- The number 100 is hard coded. The actual values you use will
-- depend on the number of elements in pList, and how large
-- pNumber is
pNumber = aNumber
pCount = pList.count
tGenePool = me.mGenerateGenePool(100)
repeat with i = 1 to 100
me.mStir(tGenePool)
end repeat
return me.mPickBestFit(tGenePool)
end if
end mFindSolution
on mMerge(me, aNumberSource, aList) ----------------------------------
-- SENT BY: new(), mFindSolution() or from a different script
-- INPUT: <aNumberSource> should be a number or a list of numbers
-- <aList> is a list of numbers
-- ACTION: Adds any float or integer numbers in aNumberSource to
-- pList
--------------------------------------------------------------------
case ilk(aNumberSource) of
#integer, #float:
aList.add(aNumberSource)
#list, #propList:
i = aNumberSource.count
repeat while i
tItem = aNumberSource[i]
case ilk(tItem) of
#float, #integer:
if not aList.getPos(tItem) then
aList.add(tItem)
end if
end case
i = i - 1
end repeat
end case
end mMerge
-- PRIVATE METHODS --
on mGenerateGenePool(me, aCount) -------------------------------------
-- CALLED BY mFindSolution()
-- INPUT: <aCount> is a positive number of genes to be created
-- RETURNS: a list of lists, each of which contains a random
-- number of randomly chosen items from pList. Certain
-- items may appear twice in any given sublist
--------------------------------------------------------------------
tGenePool = [:]
tGenePool.sort()
if not pList.count then
-- We can't create any genes
return tGenePool
end if
repeat while aCount
tGene = me.mRandomGene()
tError = me.mError(tGene)
tGenePool.addProp(tError, tGene)
aCount = aCount - 1
end repeat
return tGenePool
end mGenerateGenePool
on mRandomGene(me, aCount) -------------------------------------------
-- CALLED BY mGenerateGenePool()
-- RETURNS: a list which contains a random number of randomly
-- chosen items from pList. Certain items may appear
-- twice
--------------------------------------------------------------------
tGene = []
tError = pNumber
i = random(pNumber / pList.min())
repeat while i
tGene.append(pList[random(pCount)])
-- Ensure that genes don't get too fat
temp = me.mError(tGene)
if temp < tError then
tError = temp
else
exit repeat
end if
i = i - 1
end repeat
return tGene
end mRandomGene
on mError(me, aGene) -------------------------------------------------
-- CALLED BY mRandomGene(), mGenerateGenePool(), mStirGenePool()
-- INPUT: <aGene> is a list of numbers
-- RETURNS: a number indicating how close a fit aGene has to the
-- target number
--------------------------------------------------------------------
tSum = 0
i = aGene.count
repeat while i
tSum = tSum + aGene[i]
i = i - 1
end repeat
return abs(tSum - pNumber)
end mError
on mStir(me, aGenePool) ----------------------------------------------
-- CALLED BY mFindSolution()
-- INPUT: <aGenePool> is a list of lists of numbers
-- ACTION: Deletes the worst fitting genes somewhat randomly, then
-- crosses existing genes randomly to rebuild the
-- population
--------------------------------------------------------------------
tCount = aGenePool.count
-- Delete some (most?) of the less fit
tLowCount = sqrt(tCount)
repeat with i = tCount down to tLowCount
tFit = aGenePool.getPropAt(i)
if random(tFit) > sqrt(tFit) then
aGenePool.deleteAt(i)
end if
end repeat
-- Rebuild the population by crossing existing genes
repeat with i = aGenePool.count to tCount
tGene1 = aGenePool[random(i)].duplicate() -- copy a gene
tGene2 = aGenePool[random(i)] -- may be the same gene
tGenes = tGene2.count
j = min(tGene1.count, tGenes)
repeat while j
if random(2) - 1 then
-- Replace a number in tGene1 with a random number from tGene2
tGene1[j] = tGene2[random(tGenes)]
end if
j = j - 1
end repeat
tError = me.mError(tGene1)
aGenePool.addProp(tError, tGene1)
end repeat
end mStirGenePool
on mPickBestFit(me, aGenePool) ---------------------------------------
-- CALLED BY mFindSolution()
-- INPUT: <aGenePool> is a list of lists of numbers
-- RETURNS: a list of those unique combinations which have the
-- best fit
--------------------------------------------------------------------
tBestFit = []
tTightFit = aGenePool.getPropAt(1) -- lowest error
tCount = aGenePool.count
repeat with i = 1 to tCount
tFit = aGenePool.getPropAt(i)
if tFit > tTightFit then
-- This solution and those following are less accurate
exit repeat
end if
-- Ensure that this solution is unique
tGene = aGenePool[i]
tGene.sort()
if not tBestFit.getPos(tGene) then
tBestFit.append(tGene)
end if
end repeat
return tBestFit
end mPickBestFit
[To remove yourself from this list, or to change to digest mode, go to
http://www.penworks.com/lingo-l.cgi To post messages to the list, email
[EMAIL PROTECTED] (Problems, email [EMAIL PROTECTED]). Lingo-L is for
learning and helping with programming Lingo. Thanks!]
