Optimizing Algorithms on runtime

[islamfaisal]

Hello,

I've come up with a new idea, which is analyzing and optimizing algorithms on running time. This means that algorithms can develop as long as they run. For example, on running numerical algorithms we can analyze the output for MANY different test cases and detect some special test cases if any to add to the algorithm which may reduce the average running time. If you consider someone who wrote a primality check algorithm without noticing that every even number (except 2) can't be prime. His algorithm may be updated and will do better on average. Another one wrote an algorithm for finding Combinations and didn't notice that C(100,99) and C(100,1) are the same will be much helped by this analyzer.

Now my questions are:
Should I build an application to work with all algorithms or even numerical ones?
OR Should I choose a couple of algorithms to prove my principle on?
Does My project's idea differ from MatLab, GNU Octave and other numerical software functions or they include them? I guess they don't analyze algorithms?
Any guidance would be helped.

PS: I have 2-3 months to finish the project.
I am good with C,C#, basic algorithms & basic analysis of algorithms.
I may learn statistics, machine learning or numerical if important.
Thanks our dear experts,

[vysarge]

Hey islamfaisal!

Correct me if I'm wrong, but I think what you want to do is produce a program/algorithm to analyze and improve the runtimes of other algorithms?

As far as I know, MatLab and similar applications don't analyze the code and algorithm itself with the purpose of optimization; rather, if they have any optimization, it'll be in compiling and information storage. So a program like the one you're proposing would be fairly new.

Personally, with two months to complete a project, I'd recommend sticking with numerical algorithms, or even with a specific set of algorithms, such as primality algorithms or the like. That way, it would be much quicker to implement, debug, and test your code, without the risk of hitting a wall and being unable to complete your project.

I'd also recommend that you take some time to look at current optimization strategies- a Google search of 'optimization algorithms' might be helpful. Perhaps you might want to look at genetic algorithms as well- I've heard good things about those.

If you have additional questions or want clarification, please feel free to ask! Good luck!

[islamfaisal]

Vysarge,

Thanks for your reply!

Correct me if I'm wrong

Yes, this is what I'd like to do.

I have a couple of questions.
1) Is this project a scientific research or an engineering design?
2) I have an experimental fair on 25th November. What do you suggest for me to finish in this short time? There is no judging or dues in this experimental fair. However, it's to get students' feet on the right way.
3) Should I read about mathematical optimization itself?
4) How much workload would be fairly enough for this project? 10 Hours/week?

[hhemken]

islamfaisal,

This is a very interesting project. It embodies both math and engineering, so you can emphasize one or the other or both, as you wish.

I'm doubtful that there is any general way to optimize all kinds of algorithms irrespective of their domains or details. I agree with Vysarge, pick a class of related algorithms and focus on them. By Nov 25 you should be able to write a program that can optimize one or a few e.g. primality algorithms. They would have to be suitably instrumented so that your optimizer can watch what they are doing, what goes in, what comes out, timings, memory use, and whatever else you can think of.

Two broad approaches are 1) finding patterns and optimizing the operation of the algorithms based on them, and 2) creating rules and applying them somehow within the algorithms. One is machine learning, the other is sort of rule-based AI. For Nov 25, keep it as simple and clear as possible, but see if you can successfully optimize at least a couple of algorithms, sketch out your approach in a minimally functional test program, or some similar not-too-ambitious milestone.

Vysarge's suggestion to use genetic algorithms (GA) is ambitious, but would allow you to learn some very interesting notions about how things work. If you can parameterize the algorithms in such a way that "chromosomes" holding the parameters (the more parameters the better, the greater the range of possible values for each the better) are amenable to the GA process, you might be able to find some genuinely unexpected optimizations. You would learn one or two secrets of the universe!

As to questions 3 and 4, don't overextend yourself or neglect the rest of your school work or personal life. Ultimately, though, you must let your heart be your guide.

Good luck!

Heinz

[islamfaisal]

Hello,

Thanks for reply! I've decided to let the first milestone of the project analyze input, output and running time. I'll work with some numerical algorithms. I 'd like to know what topics in Machine Learning can help me in analyzing the data, checking for special test cases, symmetry. I'd like to know as well how can I deal with the input code. For example, If I wrote the algorithm to process code in C. It wouldn't be fair to write a library to help me detect loops, conditionals and their behaviour. What library or something like that should I use?
Genetic Algorithms look very interesting, it is worth going into! However, can you please explain more or give me a resource explaining about these "chromosomes" holding parameters?

Thanks & Regards,

[hhemken]

islamfaisal,

You can easily google for it, there's quite a lot of info out there. Here's one with some (supposedly) working Java code:

http://www.theprojectspot.com/tutorial- ... eginners/3

In that example the chromosomes are just strings of 0s and 1s, and the object is to evolve a population until an individual matches the target string.

In your case the fitness criterion can be anything you want. For example, you can encode some integer parameters as 0s and 1s and concatenate them all into a string and run the GA algorithm on a population as in the example above. The fitness criterion could be to 1) convert the string of 0s and 1s back into integers, 2) use the integers as parameters into an algorithm, to choose what functions the algorithm uses, or to somehow vary the way the algorithm works, and 3) to measure how efficient that algorithm variant is and use that result as a fitness score. As you can see, it's a pretty open ended mechanism that you can adapt to your needs and imagination.

There are many other things you can do. Just google "machine learning algorithms open source" or something similar. There's a lot of stuff out there.

Good luck!


Heinz

[islamfaisal]

Hello again our dear experts,

I've nearly finished my representation and algorithm for optimizing primality test with Genetic Algorithms. However, I am going to use a project to implement my Genetic Algorithm. Is this OK? or Shouldn't I use this library code?

http://code.google.com/p/genericga/

Thanks & Regards,

[hhemken]

Islamfaisal,

You can write your own or use an available library, whichever works best. Note that developing, debugging, and testing your own library with known inputs and outputs adds more work.


Heinz Hemken