wilmott.com

Hi. I'm a user of genetic algorithms, but by no means an expert. My question is not directly related to finance, but I have found so many knowledgeable people here, I figured it was worth a shot to run this by you.I have a GA to solve the following problem: I want to travel a certain finite distance, D, in a finite discrete number of steps, N; so, my path is a vector (d_1,d_2,...,d_N), with d_1 + d_2 + ... + d_N = D and d_i >= 0 for all i = 1,...,N. I have a cost function, C, and I'm seeking the minimum cost path. The cost function can be nonlinear and nonstationary, but it is separable in the sense that C(d_1,d_2,...,d_N) = C_1(d_1) + C_2(d_2) + ... + C_N(d_N), and C_i(0) = 0 for all i. Let's assume for now that I have programmed the GA correctly. Suppose I change the problem in one respect only, increasing the number of possible time steps to M > N; the cost function remains the same at the first N steps (and I have definitions of the remaining time step cost function pieces, C_{N+1},...,C_M). Any path for the N-step problem, (d_1,d_2,...,d_N) can be expanded to the M-step problem as (d_1,d_2,...,d_N,0,...,0), with the same original cost. It follows that the minimum cost for the M-step problem is no greater than the minimum cost for the N-step problem. But my GA doesn't always produce a better solution; in fact, as M grows larger, the frequency of M-step minimum cost solutions with higher cost than the N-step minimum cost solution increases. This doesn't shock me, because I'm searching a larger space, and I haven't changed any of the GA parameters yet -- same number of chromosomes, mutation rate, etc. My open-ended question is, what are the most effective ways to address this issue? For example, I could just toy with the basic GA parameters, such as number of chromosomes, mutation, crossover, etc. I could also do something like the following: precompute solutions for a lower number of steps, and use them as parent chromosomes for the higher number of steps (of course, this slows me down a bit). Anyway, I'd appreciate any guidelines you can offer. Thanks! -- TMK -- 212-460-5430 home 917-656-5351 cell

Hi,You seem to describe the typical Traveling Salesman Problemhttp://en.wikipedia.org/wiki/Traveling_salesman_problem If you are using MATLAB go to the FileExchange of MathWorks search for TSP, you will find many examples from which you can investigate You can also look at another method called Particule Swarm Optimization (PSO)which can be easilly implemented. Google for PSO TSPRegardsBrahim

Hi, Brahim.Thank you for responding. I don't think my problem maps easily onto TSP, evidently I didn't present it very well. It's really more of a partition problem. Perhaps a concrete example would clarify. Suppose I have to travel four miles in two days. I could go all four miles on the first day, or stay home the first day and do it all the second day. Or two miles each day. Or three, then one. Or pi miles, and then the remainder (four - pi). Etc. Each possible split has a cost. I want the split with the minimum cost. Now suppose I give myself three days to do the same four miles. I could still do all four the first day, or three and one, etc. Now I also can try one, one, and two if I like, or cube root of two, e, and the rest. I have more possibilities, but all the old possible paths remain, and their costs are the same in the three-day scenario as they were in the two-day scenario. So the least cost two-day split is a candidate for the least cost three-day split, but there may be a lower cost three-day split that doesn't finish within the first two days. For certain types of cost functions, I know that the two-day solution is best for the three-day scenario as well. But when I run my GA, I nearly always get a three-day split that costs a wee bit more than my best two-day split, even if the proposed three-day solution actually finishes in two days. I'm pretty sure the reason for this is that I'm using the same GA parametrization to search a larger space. If I use a two-day solution as a chromosome in the three-day evolution, then I'd be guaranteed to do no worse than the two-day solution. That might be the most practical approach, although it seems a bit inefficient (plus it doesn't really help when the solution to the restricted problem is not close to the optimal solution to the full problem). Anyway, I hope I illuminated the problem!-- TMK -- 212-460-5430 home 917-656-5351 cell

Hi,I think that there are lots of packing algorithms especially incomputer graphics. Looks also for scheduling algorithms. I wouldgo at your problem by clearly specifying the cost function and then maybe try use a different optimization algorithm (one thatperfoms well with constraints). It is always better to try different methods especially if you think that the GA is not perfomring well.The learning process is good experience !RegardsBrahim