Innovative Production Machines and Systems Conference

In this version, some of the parameters like neighbourhood patch size (ngh), compare to continous version of the algorithm, are not in use any more.
Also, I have been trying to reduce some other parameters. I tried some parameters recently, especially "e" and "nep". Without this parameters algorithm is still able to achive same results at the very least.
Regards,
Ebubekir

Hi Afshin,
Thanks for the nice questions. I tried to give some answers to your questions:

1. In this application, especially recruitment is a curicial part of the algorithm. So, number of bees around the selected sites (including elits) needs extra care. However, population size is another parameter needs to be optimised as we did for other applications before.

2. As we also emphasizes in the presentation and the paper, the representation of a candidate solution (CS) is as follow:

CS(xi)={1,2,...,M / 1,2,...,N}

Each candidate solution will have both machines (M) and parts (N) in a string which represents the machine-part incidence matrix.

3. As a neighbourhood search technique, we deployed a modified 3-Opt + Simple Swap combination. Modified 3-opt for faster progress, simple swap for tuning the solution quality.

Best Regards,
Ebubekir

One more thing, in the neighbourhood search "patch size" parameter is not in use anymore...

Hello Ebu Bekir,

How does the modified 3-opt work?

Thanks

Sameh Otri
PhD Research Student

Modified 3-Opt is a combination of pure 3-opt and 3-opt / simple swap in it. Using a probabilistic value, while some bees goes for pure 3 opt, some others goes for 3-opt/simple swap.
A simple example for 3-opt and 3-opt/simple swap can be simplified as follow:

Assume that a string of 16 machines:

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16

After 3-opt
1-2-3-9- 10-11-12-13 - 4-5-6-7-8 - 14-15-16

After 3-opt/Simple swap
1-2-3-9- -12-11-10-13 - 7-4-6-5-8 - 14-15-16

a nice description can be found in The Traveling Salesman Problem: A Case Study in Local Optimization, via wikipedia

Hi Vlado,
Thanks for your nice and detailed questions.
Well, regarding the objective function, there are so many objective functions are available; you can see some of them in Serker 2001.
As we emphasized in the paper this is one of the first application of the bees algorithm to combinatorial problems. You are right we could use any other kind of objective functions but first we wanted to see the performans of the algorithm by using a relatively "well-behaved" function. However, as we shown in our results the bees algorithm works well with this kinds of problems. And I am already working on the problems with an objective function added weights on the importance of inter/intra-cellular flow. I'm hoping to present my results soon.
For the local search, there we still have similar neighbourhood search for combinatorial version of the algorithm. However, this version is not contains 'patch size' concept because of the nature of combinatorial problems. Instead, we deployed modified 3-opt and simple swap operators. But, we still have the recruitment concept 'around' selected sites.

Best Regards,
Ebubekir

Thanks Vlado... Thats better...

Ebubekir

Looking at your other comments, it looks like you are using local 3-opt. Have you investigated starting with a larger k-opt neighbourhood, gradually reducing k?

k could be a function of your goodness measure.

How does restricting the size of the site/patch reflect on the performance of the algorithm. Have you tried similar 'fixed radius' approach on other problems? When does it work better and when worse?

Oops, I added my other comment a bit early =)

3-opt, essentially defines a neighbourhood in the problem solution space with a distance 3 - three changes, hence my question. It is true that with a high number of dimentions, you have a relatively big number of possible neighbours, but it is the same in the continuous function optimisation case.

...and register

with the website. It is completely free, and unrelated to registering as a payed participant. The latter includes among other things the printed proceedings.

We want the papers to be accessible for free to everyone, but need to juggle the copyright, thus the requirement for registration on the website.

Actually, I have tried 'some'-opts but at the end of the day 3-opt seems to produce best results with this problem so far . But, gradual reduction of k another good idea, worth to try it...
Regarding 'fixed radius', as I mentioned before and in the paper, in this version of the algorithm there is no more metric radius defined as we defined in our continous version. So, there we have no worries of defining this radius.

Regards,
Ebubekir

I'm not sure I understood this %100...

Thanks Sena

Its very nice to see a Turkish colleague in this conference with nice questions. I hope you are enjoying with the bees algorithm. Actually, we were expecting your paper as well, in this session. Anyway, next year I'm sure we will have some strong papers from our Turkish colleagues.

Well, here I have some answers to your questions:
1. All parameters have been selected by trial and error method. But, no worries you don't have much choise...
2. No, we don't have any ratio to determine the values of the parameters all trial and error. Actually, if you look at the paper, you can see that we are using same values of parameters for all problems in this application.

Regards,
Ebubekir

mmm, k-opt - is just a fancy way of saying - let's make k atomic changes to our 'thing', whatever that thing is, whatever we define as atomic change.

If you forget for a moment about the 'thing' itself and consider it a point, let's say in some metric space, and a 'change' can be considered a unit move along one of the dimensions of that space. Independent of the definition of space and 'change', the upper bound of the distance of k-opt is not larger than k units of the space. So you can treat change as movement in that metric space. How exactly you define distance doesn't really matter, as long as your abstraction is preserving the properties of the 'thing' and is reversible.

The beauty of this treatment is that you don't really need to know the dimensionality of the space to move in it - in most cases you could find it, in others the number of dimensions can change. For the 'classic bees' treatment this is a good feature. You can think in terms of patch radius, and apply the same heuristics ad in the 'classic' case.

Actually, the same applies to a lot of other methods, for example you can lift combinatorial problems to be treated by PSOs this way. I think there are quite a few examples of that, maybe not explained using the same words.

Well, Vlado I like the way the debate is going. However, if you look at this fancy term, k-opt, you can talk about k atomic changes in metric -continous- space. But if you go to discrite -combinatorial- space there is the real trouble for your metric understanding. The concept 'change' needs to be defined completely different ways.

But, there is another understanding may support your point of view: you can consider k-atomic-changes, 1-opt, 2-opt, 3-opt... as your closest neihbours in combinatorial and k-opt is the far neighbours. But, here another question is rising, how you are going to define this 'atomic' changes in combinatorial space.

Regards,
Ebubekir

In addition to your edited comment...
I saw PSO at the end of your comment. Well... we can deal with the combinatorial like PSO, but I think, we don't need it that much. Because when we go to combinatorial space, the bees algorithm is not changing its way of behaving like PSO. Because of its structure PSO needs to change its essential parts to deal with combinatorial. But in our case, we have no such worry. Just way difinnig the neighbourhood needs to be modified as we did in this version. But ofcourse there is so much to do...

Not that much different ways.

Let's say A is the set of all strings encoding some solution. We can move from one string to another in a number of ways. The exact definition of move depends on the combinatorial problem. In this case let's consider for simplicity only one kind of move - swap two positions.

The above defines an algebra, let's call it Sw <swap,A>.

The continuous case defines similarly an algebra Cm <move,N>.

What I'm saying is that the combinatorial case can be solved using an unmodified 'continuous' algorithm if we find a way to lift Sw -> Cm. Which essentially means that we need to find to maps, let's call them lift and unlift, such that:

• unlift( lift( A ) ) = A, i.e. lift . unlift = id
• lift( unlift( N ) ) = N, i.e. unlift . lift = id
• swap = unlift . move . lift
• move = lift . swap . unlift

(the dot means compose, right associative)

In essence - we need to preserve the properties of the original (combinatorial) space 'points, regardless what we do in the lifted (continuous) one. We need to be able to come back to the combinatorial space.

In this case the definition of swap is relative to the original point. So in the lifted space move should mirror that. Notice that both swap and move can be expressed in terms of each other. This means that all we need is to have a definition of one of them, in order to use the other.

Now to the bees. In the original, the domain is some N^m. If a solution is selected a patch is formed(moved) centered around that solution and a number of random points are drawn inside that patch. The only thing we don't have yet is the process of randomly drawing a point inside a patch - rand(P).

swap is the smallest possible change, unit distance, atomic as defined by Sw, then we can say that |lift(swap(A))| -> 1 and lift(swap(A)) is a unit vector in N.
swap . swap . swap .liftwill be within a radius of 3 relative to the argument. You noice that I skip the arguments - I'm only trying to put the schematics down - the rest is trivial.

What would be the meaning of rand . unlift?
A procedural definition will do nicely. randSw Select randomly positions p1 and p2, swap those positions in a string a.. This doesn't require any knowledge of the lifted domain. But we can rand = randSw . lift. The rest of the above rules should be valid as well.

All this means that we can use the original bee algorithms structure, by simply replacing rand(x,r) with lift(randSw(A)).

But wait a minute, if that is the only difference - the rest of the algorithm is already generic enough, or works with the co-domain (value) of the objective function, then why do we need all of this lifting?

So Look ma - no lifts - the structure is the same, and all this lifting and unlifting is just a tool to prove that the original structure of the bees algorithm doesn't need to be modified to be able to work on combinatorial problems. The trick is that all this lifting business helps to understand what do we need to define, in order to use the unmodified, structure wise, algorithm.

To be fair - the above discussion is very rough, in the middle and around the edges, but for illustration of the methodology it should do.

In this case, the definition of randSw -as in your representation- is a key issue for this process. But, I'm not sure, this random generation is possible or not!
Including this, I noticed that you are saying:

What would be the meaning of rand . unlift?
A procedural definition will do nicely. randSw Select randomly positions p1 and p2, swap those positions in a string a.. This doesn't require any knowledge of the lifted domain. But we can rand = randSw . lift. The rest of the above rules should be valid as well.

All this means that we can use the original bee algorithms structure, by simply replacing rand(x,r) with lift(randSw(A)).

Well, my answer/comment is that in this version I'm already deploying this process 'Select randomly positions p1 and p2, swap those positions in a string a'. And the only modification is instead of sending bees within a predefined boundaries, I'm sending them 'around' that candidate solution (or scout bee) using modified 3-opt and simple swap. Including this, reducing a parameter.

Also, I can not agree with you about what you are saying about proving that the bees algorithm has the same original structure for both continous and combinatorial, using this lifting and unlifting process:

'all this lifting and unlifting is just a tool to prove that the original structure of the bees algorithm doesn't need to be modified to be able to work on combinatorial problems'.

Because, the structure is same! There is no need to prove such thing. The only change is about how to send bees around a candidate solution, i.e. rand(x,r) which needs modification in your randSw case.

Regards,
Ebubekir

well, the structure is not exactly the same, or I might misunderstant it. You are using a fixed radius of a patch. By patch here I mean the neighbourhood of a candidate solution (bee?).

Assuming that opt-3 is opt-2( opt-2(x) ), similarly with opt-3-simple-swap, this means that your radius is <3, that is 1 or two atomic operations.

There is a need to prove that it is legal to apply the method. Since we believe it is in the continuous case, using the lift.x.unlift construct proves it by induction. It is a stronger statement that they are simply looking the same. By construction they are proved to have the same meaning.

Yep, I do believe you are using the random selects around a candidate solution. Apropos, how does that differ from the original bees? As far as I understand it a patch is an area around a pre-selected candidate solution.

The write-up above was about more to answer your concerns about combinatorial PSO and the selection of atomic operations.

I did it for bees, since your paper is about the bees algorithm, but the same methodology could be applied for PSOs, or for choosing a GA coding etc... It would be too long to do it in this thread.

Choosing atomic ops is not trivial, but you can test your choice by proving that using only your chosen operations you can define a procedure for counting the set of solutions (the domain of the objective function). Assuming that it is countable to start with. The art of that choice comes with understanding the domain of your objective function. For an example of PSO for TSP where the operators are 'worked out' using a similar process
Discrete Particle Swarm Optimization. Notice how the author defines the different operations present in the classical PSO for the travelling salesman problem case. Each definition is equivalent to op.lift in the above notation.

Ok, if you are assuming that 3-opt is a patch size yes I'm using a fixed patch size. However, don't forget this is not only 3-opt, I'm deploying modified 3-opt and simple swap. But anyway, I think this can not be defined as a kind of metric 'patch size' like in continuous case. If you remember GA case for instance, is it possible to define mutation or crossover operators as a kind of 'patch size'? I think 'local search' is more appropriate for this kind of situations.

Well, if we came to difference from original bees, I may say that the concept 'around a candidate solution' is re-defined in this case. As you understood, a patch is an area around a pre-selected candidate solution.

Regarding PSO, please give me couple of hours, I need to study the file a bit more...

yes, it is possible to define mutation and cross-over in terms of distance from the original(s).

For example if you use bit-encoding - distance could be the the number of different bits (xor + count the 1s).

Well, thats another nice question. We are comparing the bees algorithm with 5 different algorithms including GA. We just used best results from literature. However, in this paper we decided to follow literature, we didn't run other algorithms on our own. And we couldn't find any appropriate application using PSO and ACO for this problem. So thats why PSO and ACO aren't in the paper. May be in the future...

Yes, we could use some extra results as well, but I think this data sets already representing simplicity and/or complexity of all. However, another reason may be; some of the data is not easy to access like 15x10 which you are mentioning in Mak et al.

Regards,
Ebubekir Koc

Even you define as a metric mesure, is it possible to control this metric measure? Think about our case in continuous version. We can define a (+,-) patch size and we can control it. But in this case, even you define it in a bit coding, you can not control it like continuous case. And I think there no difference between bit-encoding and real numbers (i.e. 1,2,...,n) when you come to 'distance' and controling this distance.

you don't have the resolution of real numbers, you have 'manhattan distance' instead. You do have control, or you could have control - you can decide how many changes to make. That is why I was using 'atomic' earlier.

Well, in this case, the question is: how?

However, I have another concern about lifting up and down. When you somehow lift up to a 'continuous' space, ok its acceptable that you can do some metric neighbourhood search, but how you will convert (or lift down) these points into combinatorial space. And how you will know that you are 'around' that point.

We are looking at the issue from different angles, I'll prepare a writeup, where I'll describe the background and show on examples what I meant with my comments.

Thanks Vlado for preparing a document of your valuable comments.

It would be even greater if you can kindly give us a short presentation in our Bees Council next Wed 18 or 25 of July.

Regards,

Sameh Otri
PhD Research Student