c******r
发帖数: 6 | 1 I have a mathematical problem which I abstracted from my engineering
background. Unfortunately, I don't know how to solve it. Therefore
I'd like to ask the expert in this field who can give me a help or
if you can give me a direction for that.
Thank you very much.
=========================================================================
Problem:
Given a undirected graph (V,E), there are N nodes N1, N2, N3, .....
We are going to assign each node a distinctive number starting from 1 to N.
For each | a***u
发帖数: 72 | 2 严格解不晓得.
近似解可以有两种算法好像很适合.
1) Genetic Algorithm;
2) Monete Carlo Annealing;
如果体系比较大,两种算法scaling应该还可以.GA能找到多个优化解,如果解域是nonconve
x的话.当然没有一种算法能保证找到对应于exact solution(if exists)的解.
【在 c******r 的大作中提到】
: I have a mathematical problem which I abstracted from my engineering
: background. Unfortunately, I don't know how to solve it. Therefore
: I'd like to ask the expert in this field who can give me a help or
: if you can give me a direction for that.
: Thank you very much.
: =========================================================================
: Problem:
: Given a undirected graph (V,E), there are N nodes N1, N2, N3, .....
: We are going to assign each node a distinctive number starting from 1 to N.
: For each
| f**n
发帖数: 401 | 3 This problem is a combinatorial optimizatin problem. If you don't care about
"real" optimum, as pointed out by another worm earlier, GA, Monte Carlo, NN
or any other fancy optimization techniques should be OK.
(1) If real optimum is of primary importance, it can be formulated as an integer
programming problem, or more strictly speaking, a binary optimization
problem. You might want to do the following
define decision variable d(i,j) such that
d(i,j)=0 if N(i)!=j
=1 if N(i)=j
and you need t
【在 c******r 的大作中提到】
: I have a mathematical problem which I abstracted from my engineering
: background. Unfortunately, I don't know how to solve it. Therefore
: I'd like to ask the expert in this field who can give me a help or
: if you can give me a direction for that.
: Thank you very much.
: =========================================================================
: Problem:
: Given a undirected graph (V,E), there are N nodes N1, N2, N3, .....
: We are going to assign each node a distinctive number starting from 1 to N.
: For each
| a***u
发帖数: 72 | 4 Don't know for sure. The dimensionality of the "Graph" plays a role here. For
both GA, and Monte Carlo, no a prori knowledge about convergence is there.
It's too hard to consider, unless the Graph is more specific, and the domain
of solution is clears defined.
Anyway, since the individual cost function has a simpel form here, the
derivatives of f(x,y) also have simple forms.
An equation set of N dF/dx_i ==0 is already in a close form. N equations for N
unknown varibles. With those varibles known
【在 f**n 的大作中提到】
: This problem is a combinatorial optimizatin problem. If you don't care about
: "real" optimum, as pointed out by another worm earlier, GA, Monte Carlo, NN
: or any other fancy optimization techniques should be OK.
: (1) If real optimum is of primary importance, it can be formulated as an integer
: programming problem, or more strictly speaking, a binary optimization
: problem. You might want to do the following
: define decision variable d(i,j) such that
: d(i,j)=0 if N(i)!=j
: =1 if N(i)=j
: and you need t
| f**n
发帖数: 401 | 5
Thanks. I get you point here.
Actually I also mentioned this in my second point. What you are saying
is try to find the NLP relaxation for the original integer programming
problem, I think. But even if the relaxation can be solved easily, it is generally
still very difficult to get the real integer optimal or sub-optimal solution
solutions. That's why combinatorial problems are so hard, though it is only
one step away from other optimization problems.
【在 a***u 的大作中提到】
: Don't know for sure. The dimensionality of the "Graph" plays a role here. For
: both GA, and Monte Carlo, no a prori knowledge about convergence is there.
: It's too hard to consider, unless the Graph is more specific, and the domain
: of solution is clears defined.
: Anyway, since the individual cost function has a simpel form here, the
: derivatives of f(x,y) also have simple forms.
: An equation set of N dF/dx_i ==0 is already in a close form. N equations for N
: unknown varibles. With those varibles known
| c******r
发帖数: 6 | 6 Hi,
Sincere thank to Ahhaau and Fern for their discussions about this problem. :)
Two points I want to make:
1. I've tried to use simulated annealing to do iterative improvement. But
because of the effect of parameter tuning, the algorithm is kind of slow.
That's why I want to find a computationally effecient algorithm to solve it.
If not, at least a good heuristics.
2. I also tried to formulate the constraints as integer constraints. But
notice that the cost functions may not be linear, so solv |
|
