New Ideas
After meeting with my supervisor, two things have been clarified.
First, equipment type and so on is not going to be consideration. Two things that got into consideration are:
- Distance between nodes
- The location of the equipment
With this, we wouldn't implement Floyd Algorithm but we use GA straight to determined the best equipment position.
Matrix representation would be:
- an M x M matrix with M is the number of nodes involves in the network.
- the connection between nodes will be marked by the distance between the node
- if there are no connection, 0 will be filled into the respective position in the matrix.
Possible Chromosome Structure
Finally, some light!!
first, use a connectivity matrix to structured how the network shaped. In this matrix contains data about the length of connectivity of each nodes.
second, the chromosome only contain data about cable type that goes
towards that node, and the type of equipment in that node. If the node doesn't have any equipment (the cable just run through), it will have a flag to state that condition.
third, I will need a function to determined whether the generated solution is permitable or not. I fear that since there are two interconnected data (cable type and equipment) in the chromosome, we can't just change 1 bit and hope that it will still be in the solution domain. Example: one node would handle 4 customer ends. However, the cheapest way is actually by using 3 cable, split 1 cable, distribute the split cable and cable 2 and three to the customers. See here, the split and the number of cable parameter is interconnected with eachother. Each changes that happens on the first parameter would demand some adjustment on the other paramater.
head hurts, got to sleep, laters..
Network Visualization
My next idea is to visualize the network. I take this step so it would be easier for future debugging. First step is, to create a matrix with the size of N X M. With N as the number of DP in network, and M as the number of customer nodes. Next, we populate the matrix with connectivity data like the distance between two nodes.
We could then draw nodes and their connectivity based on the matrix.
I'll be using JBuilder for this. Luckily, there's been an assignment which modules I could use for this purpose. Hopefully not much changes needed for this.
Floyd's Algorithm
Making some slow progress here.
Okay, some new information that could be helpful.
1. We didn't use GA to determined which Distribution Point (DP) that the network are going to use. We employ
Floyd's Algorithm to determined the shortest way to customer nodes.
2. We used GA to determined cable types, equipments (router types), connection types and find the cheapest solution.
3. A problem that occured to me is when there's a DP that just connected
one customer node. In the first step using Floyd's algorithm, that DP is surely will be counted, while the most possible way is just extend a cable from a nearest DP as that would be cheaper.
4. Considering that no. 3 is not feasible due to that single customer is too distant to connect without using that additional DP spot, I need to find a way to include some additional parameters such as maximum cable length permitted.
5. Regarding no 3, I have this idea that we could probably solve it using the GA. Acknowlegding that DP, but employing 0 equipment as the cable just pass through.
This GA thingy
Okay, from reading
this lady blog, I think it's a good idea to put what I have found so far about my disertation in a blog. It would help me on reviewing them later. So, let's just called this my own knowledge base system.
Here's what I found so far about GA (Genetic Algorithm).
GA is a search mechanism that use Darwinian method of survival of the fittest to find the best solution on the given problem. First, it randomly generates a group of solution strings called a
population. A solution string is called a
chromosome. We then check whether this solutions is feasible or not. If not repair them. Then, a fitness function evaluates which of these chromosomes is the closest to the solution (the fittest). After we choose the closest solution strings, and execute 'genetic operations', which are crossover and mutation. Crossover would pick randomly of the selected 'fittest' solutions and interchange parts of the two chromosomes to make a new one. Mutation is by randomly altering one or some of the bits in the string. These two operation would make a new generation of chromosomes. We run these new generation into the fitness function and decides which of these solutions would make it to the population or not.
After that, we repeat the steps on the new population, until we find the solution.
That's about all I got right now.
Things that are still vague:
1. How the hell do I create a string that could represent a
whole network??
I got an idea of using direct encoding, which put represent network by using a matrix, and then represent the matrix into a string. It's like coordination system, we the x axis that list all the nodes, and we have the y axis that list all the nodes too. So say, we want to tell that there's a connection between node 3 and 4, we just put 1 in the (3,4) cell of the matrix. The thing is, I need not only just representing the connections, but also in representing, what kind of cable that we use, what kind of router that we used. How do I encode router and cable types into the chromosome string.
2. I only know how the mutation and crossover works in the binary encoding. But if I got around of point 1, then I don't think that would be using binary encoding.
my head ache, and I haven't put on the covers on my bed, oh well.
