Data structure and Ant Colony Optimization in C
$750-1500 USD
Paid on delivery
This project will involve working with Ant Colony Optimization (ACO). The data structure will be a tree and goal would be to find best path. If you have experience let me know I will send you details about the project.
Please check attached file.
This project involves
User inputs:
1. Depth of tree (N)
2. Initial value of variable price $ (A)
3. Volatility of A (σ)
4. Range for congested price
5. Percentage of nodes where variable price will be different from payoff price (Y)
Step 1 (creation of data structure)
- Each node will consist of
o Links to child nodes (and pheromone values for each edges)
o Two prices: Variable price $ (A) and Payoff price $ (B)
1. Tree will be a Binomial tree starting with an initial value of A (user input).
2. From each parent node, there will be two child nodes. These two child nodes will have A values based on volatility (σ), (A (parent node) * (1+σ)) and (A (parent node) * (1- σ)).
For example, let us say initial value of A is 10 and value of σ is 10%. So root node will have value of A as 10, and two child nodes will have values of A as 11 (A (parent node) * (1+σ)) and 9 (A (parent node) * (1- σ)) . These two nodes will have their own two child nodes with A values as (A (parent node) * (1+σ)) and (A (parent node) * (1- σ)). 11 node will have child nodes as A values as 12.1 and 9.9. 9 node will have child nodes with A values as 9.9 and 8.1.
↗
12.1
↗ ↘
11
↘ ↗
9.9
↗ ↘
10
↘ ↗
9.9
↗ ↘
9
↘ ↗
8.1
↘
Depth 0 1 2 …
3. Creation of nodes continues until required depth of tree (user input) is achieved. At this point, the tree will have 2N-1 nodes where N is depth of tree.
4. Now randomly select Y (user input) nodes from all nodes in the binomial tree.
5. For each selected node, assign random value to B for that node and next three level of child nodes based on following rules:
o Random value of B < value of A
o Value of B must be within user input range
o Give an error to user if these criteria cannot be met
Idea is to allocate random values of B in random neighborhoods.
6. For rest of the nodes (which are not randomly selected in step 4), make B=A.
Step 2: Use created data structure to calculate payouts
Programming will use some concepts of Ant Colony Optimization.
Goal will be to find best path from root node to leaf node based on highest accumulated profit. Profit at each node is calculated by A-B. Agents perform addition of profits at each node during their travel from root node to leaf node.
Programming will involve using agents (processes) with local memory (specific to each agent) and a global memory which will be shared by all agents. Local memory of each agent is updated while they are transversing the tree. Global memory is updated after all agents reach leaf nodes and is based on best path found.
1. Intialize all edges (between nodes) with initial pheromone.
2. For Each agent :
a. Start at root node of tree and move further in the tree. Agents will make decision on which path to choose based on pheromone levels. Meaning at each node, agent will have a choice of moving to either of two child nodes. Agent will follow edge with higher pheromone. If pheromone levels are same then choose path randomly.
b. At each node profit is calculated based on P = A-B. Agents keep track of profits made from root node to leaf nodes (total P). In their local copy of data structure, agents update pheromone level so more agents follow this path.
3. Once all agents reach leaf nodes update pheromone values based on best solution found found.
4. Go to Step 2. Is solution does not change then go to step 5
5. Report profit and compute time
Profit and comp time will be compared to exhaustive search of above data structure.
Program will exhaustively search each level of tree to compute best profit (A-B) and then addition of profits (at each level) to give final profit number. And time to compute exhaustive search.
Project ID: #4934574
About the project
23 freelancers are bidding on average $957 for this job
I am very proficient in c, c++ and data structure. I have 15 years c++ developing experience now, and I have worked for 5 years. Trust me, please let expert help you.
Hello, I am expert and dedicated in C/C++ based development and algorithm. I am very much interested for your project. I can complete your project quickly and efficiently in time. Details will be discussed in the messa More
Hi, I have experience with metaheuristics and Data Structures. Let me help you. I am ready to start.
Hi my friend, I am strong in C/C++ programming especially in algorithm implementation. I have deep insight into Artificial Intelligence algorithm including Genetic Algorithm, Simulated Annealing and Ant Colony Algor More
HI I have tons of experience of working in c. I have worked on graphs trees, link lists etc., I can definitely implement this algorithm. Looking forward to hear from you. Regards
I have considerable experience developing algorithms in C/C++ and I can provide you with a professional solution.
Hello. As I remember ACO is used for approximate resolving of topology problems. Could you provide more details about your project?