Exchange Heuristic and Swapping Code

nat47 has asked for the wisdom of the Perl Monks concerning the following question:

I posted a thread the other day and I didn't include any code. What I'm trying to do is: while the ideal state is still better than our current state, exchange 1 item for a different item in a leftovers array. So, the firs thing to do is check if the item to exchange fits, then check if it is a better $current_best. Right now I'm just trying to drop by order, pick first, loop through replacing the remaining items, then go back to the main loop change to second item. If state gets 'better' then the state is kept and looped through with that state. When the ideal state is met, it should stop.

This is the code I've started to write, it doesn't work and isn't done in Perl fashion...

@solution has the current set of items, @leftovers has the possible items that aren't inside @solution

while($ideal_state > $current_best)
{    my $coun = 0;

    for(my $a = 0; $a < scalar @solution; $a++)
    {
        for(my $b = 0; $b < scalar @leftovers; $b++)
        {    
            my $hold_previous = $solution[$a];
            $solution[$a] = $leftovers[$b];
            if($max_weight > totalweight(@solution))
            {
                if(totalscore(@solution)>=$current_best)
                {
                    
                    $leftovers[$b] = $hold_previous;
                }
            }
            else
            {
                $solution[$a] = $hold_previous;
            }
        }
        #print "Main loop";
    }
    
}
[download]

Comment on Exchange Heuristic and Swapping Code Download Code

Replies are listed 'Best First'.
Re: Exchange Heuristic and Swapping Code by SuicideJunkie (Vicar) on Mar 03, 2015 at 16:45 UTC
Unless your problems have extra constraints, then refusing to swap more than one at a time will allow you to get stuck in a local minima, and never find the true solution. For example, if you have a capacity/goal of 10, and your current solution is `[6]`, with leftovers of `[1,2,3,4]` No single swap will improve your score, but trading your single value for all the leftovers would get you a perfect score. In a similar way, `[5,2]` with `[4,4]` left over, and a max and goal of 8. Swapping the 5 for a 4 makes it worse. Swapping the 2 for a 4 puts you over the max. N-to-1 swaps and 1-to-N swaps also fail. The only way to get the optimal solution without making the intermediate solution worse is a 2-for-2 swap.	[reply] [d/l] [select]
Re^2: Exchange Heuristic and Swapping Code by nat47 (Sexton) on Mar 03, 2015 at 17:03 UTC
@solution1,2,3,4,5 @leftovers6,7,8 pick [0] of @solution and examine combinations 6,2,3,4,5, 7,2,3,4,5, and 9,2,3,4,5. If these are not closer to goal state then do the same with 1 so that 1,6,3,4,5, 1,7,3,4,5, etc This makes sense then, that it could run through the whole thing and not find a better solution?	[reply]