Logic Code required to be run in finite time

2 visualizzazioni (ultimi 30 giorni)
Ninad Pimpalkhare
Ninad Pimpalkhare il 18 Apr 2025
Modificato: John D'Errico il 19 Apr 2025
Hello,
I have 2 sets of data. Set 1 contains 57 complex numbers. Set 2 is the same set of complex no. but with opposite sign.
nth term in sets is defined as
Set 1 = (An+iBn)
Set 2 = (-An-iBn)
n=57
Eg:
Set 1 (2+2i , 3-2i, -4+6i......57 terms total)
Set 2 (-2-2i, -3+2i, 4-6i....57 terms toal).
Finally what I want is to create a SET 3 which consists of 57 terms. Each of the nth term in SET 3 can be either from SET1 or SET2.
Condition of SET3 is that: Finally when I take the complex SUM of 57 terms of SET3, and take the Magnitude part of the SUM (RMS) it should be the least possible minimum value out of the all possible combinations of 57 terms from SET1 or SET2.
Total no. of combinations (loop in program) that are required to be run if we want to check sum of each combination, is 2^57 which is not possible in finite time.
Is there any logical way to address this problem and get the answer.
Any help would be appreciated.
Thank you.!!

Accedi per rispondere a questa domanda.

Risposte (1)

John D'Errico
John D'Errico il 18 Apr 2025
Modificato: John D'Errico il 19 Apr 2025
Ran in:
I think you misunderstand an important idea of computing. You NEVER want to use brute force on big problems. Those problems always get far too intensive to solve. And that is what you wnat to do, checking all 2^57 combinations to minimize a result. I say you misunderstand things, because you are clearly thinking about this in terms of a loop, and the need to check every possibility. And that is the wrong way to go, since you will never be able to solve your problem. It means you need to learn to think differently on this class of problem.
Instead, this is what optimization tools are designed to solve! If I understand your question, you have a vector, for example, here I have a complex vector of length 10:
n = 10;
X = randn(1,n) + i*randn(1,n)
X =
Columns 1 through 9 -0.5185 - 1.5442i 1.0419 - 0.2209i -1.8028 - 0.6038i -1.1673 - 0.9536i 2.4249 - 1.1892i 0.0023 - 0.2715i 0.4695 - 2.0732i 1.7708 - 0.4944i 1.3844 + 1.4936i Column 10 1.7153 - 0.8265i
Now you want to chose a boolean vector B, thus a vector of length the same as X, but composed of zeros and ones. The objective is to choose B, such that
abs(dot(B,X) + dot(1-B,-X))
is minimized? So as an example, I'll choose three random vectors B, and show that we get different results for each.
B = rand(n,3) > 0.5
B = 10x3 logical array
0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0
abs(X*B + (-X)*(1-B))
ans = 1×3
4.8068 10.4720 5.1421
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
There will be some binary vector B, out of the 1024 possible such vectors in this small example that minimizes the result. I'll use an optimization tool to find the solution. Best would be a tool like intlinprog, but this is not a linear problem, so intlinprog is not an option. Our object function would be something like this:
obj = @(B) abs(X*B - X*(1-B));
But first, I can actually make the objective simpler, because we can rewrite it as:
X*B - X*(1- B) == -X + X*2*B = X*(2*B - 1)
abs(X*(2*B-1))
ans = 1×3
4.8068 10.4720 5.1421
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
As you can see, the two results are identical. This works because X is a row vector, and B a binary column vector.
obj = @(B,X) abs(X*(2*B(:)-1));
When B == 0, 2*B-1 is -1, and when B == 1, 2*B-1 reduces to 1. So it still does what you want. Regardless, now I'll use an optimization tool. GA comes to mind.
intcon = 1:n;
lb = zeros(n,1);
ub = ones(n,1);
opts = optimoptions('ga')
opts =
ga options: Set properties: No options set. Default properties: ConstraintTolerance: 1.0000e-03 CreationFcn: [] CrossoverFcn: [] CrossoverFraction: 0.8000 Display: 'final' EliteCount: '0.05*PopulationSize' FitnessLimit: -Inf FitnessScalingFcn: @fitscalingrank FunctionTolerance: 1.0000e-06 HybridFcn: [] InitialPopulationMatrix: [] InitialPopulationRange: [] InitialScoresMatrix: [] MaxGenerations: '100*numberOfVariables' MaxStallGenerations: 50 MaxStallTime: Inf MaxTime: Inf MutationFcn: [] NonlinearConstraintAlgorithm: 'auglag' OutputFcn: [] PlotFcn: [] PopulationSize: '50 when numberOfVariables <= 5, else 200' PopulationType: 'doubleVector' SelectionFcn: [] UseParallel: 0 UseVectorized: 0
opts.Display = 'iter';
[Bvec,Fval,exitflag] = ga(@(B) obj(B,X),n,[],[],[],[],lb,ub,[],intcon,opts)
Single objective optimization: 10 Variables 10 Integer variables Options: CreationFcn: @gacreationuniformint CrossoverFcn: @crossoverlaplace SelectionFcn: @selectiontournament MutationFcn: @mutationpower Best Mean Stall Generation Func-count Penalty Penalty Generations 1 200 0.6091 4.593 0 2 295 0.6091 4.168 1 3 390 0.6091 4.817 2 4 485 0.6091 4.717 3 5 580 0.4945 4.739 0 6 675 0.4945 4.72 1 7 770 0.4945 4.644 2 8 865 0.4945 4.487 3 9 960 0.4945 4.738 4 10 1055 0.4945 4.145 5 11 1150 0.4945 4.596 6 12 1245 0.4945 4.328 7 13 1340 0.4945 4.326 8 14 1435 0.4945 4.074 9 15 1530 0.4945 4.556 10 16 1625 0.4945 4.657 11 17 1720 0.4945 4.549 12 18 1815 0.4945 4.618 13 19 1910 0.4945 4.574 14 20 2005 0.4945 4.721 15 21 2100 0.4945 4.533 16 22 2195 0.4945 4.427 17 23 2290 0.4945 4.619 18 24 2385 0.4945 4.446 19 25 2480 0.4945 4.488 20 26 2575 0.4945 4.528 21 27 2670 0.4945 4.314 22 28 2765 0.4945 4.659 23 29 2860 0.4945 4.413 24 Best Mean Stall Generation Func-count Penalty Penalty Generations 30 2955 0.4945 4.519 25 31 3050 0.4945 4.346 26 32 3145 0.4945 4.42 27 33 3240 0.4945 4.816 28 34 3335 0.4945 4.648 29 35 3430 0.4945 4.557 30 36 3525 0.4945 4.762 31 37 3620 0.4945 4.625 32 38 3715 0.4945 4.488 33 39 3810 0.4945 4.31 34 40 3905 0.4945 4.477 35 41 4000 0.4945 4.599 36 42 4095 0.4945 4.127 37 43 4190 0.4945 4.621 38 44 4285 0.4945 4.373 39 45 4380 0.4945 4.631 40 46 4475 0.4945 4.305 41 47 4570 0.4945 4.186 42 48 4665 0.4945 4.588 43 49 4760 0.4945 4.311 44 50 4855 0.4945 4.267 45 51 4950 0.4945 4.513 46 52 5045 0.4945 4.636 47 53 5140 0.4945 4.867 48 54 5235 0.4945 4.432 49 55 5330 0.4945 4.621 50 ga stopped because the average change in the penalty function value is less than options.FunctionTolerance and the constraint violation is less than options.ConstraintTolerance.
Bvec = 1×10
0 0 0 0 1 0 1 0 0 0
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
Fval = 0.4945
exitflag = 1
Is that the optimal solution? We can verify it easily enough, using brute force for this small problem, as that gives us a way to check the small problem, before I go on to a larger problem where I cannot make a brute force validation.
B = dec2bin(0:1023)' - '0';
[objmin,ind] = min(abs(X*(2*B - 1)))
objmin = 0.4945
ind = 41
B(:,ind)'
ans = 1×10
0 0 0 0 1 0 1 0 0 0
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
And indeed, it works. Note that I used only a vector of length 10 to make the brute force solution a viable one. I'll redo it now with a vector of length 57.
n = 57;
X = randn(1,n) + i*randn(1,n);
intcon = 1:n;
lb = zeros(n,1);
ub = ones(n,1);
tic,[Bvec,Fval,exitflag] = ga(@(B) obj(B,X),n,[],[],[],[],lb,ub,[],intcon,opts),toc
Single objective optimization: 57 Variables 57 Integer variables Options: CreationFcn: @gacreationuniformint CrossoverFcn: @crossoverlaplace SelectionFcn: @selectiontournament MutationFcn: @mutationpower Best Mean Stall Generation Func-count Penalty Penalty Generations 1 200 0.3047 7.623 0 2 295 0.3047 6.91 1 3 390 0.3047 7.522 2 4 485 0.3047 7.41 3 5 580 0.2135 6.92 0 6 675 0.2135 6.853 1 7 770 0.2135 7.561 2 8 865 0.2135 7.285 3 9 960 0.2135 6.573 4 10 1055 0.2135 6.54 5 11 1150 0.2135 6.613 6 12 1245 0.1924 6.791 0 13 1340 0.1924 7.343 1 14 1435 0.1924 7.498 2 15 1530 0.1924 6.62 3 16 1625 0.1924 7.718 4 17 1720 0.1924 6.704 5 18 1815 0.1924 6.588 6 19 1910 0.1924 6.946 7 20 2005 0.1924 6.615 8 21 2100 0.1924 6.785 9 22 2195 0.1924 6.757 10 23 2290 0.1924 7.012 11 24 2385 0.1924 6.138 12 25 2480 0.1924 7.245 13 26 2575 0.1924 8.007 14 27 2670 0.1924 7.288 15 28 2765 0.1924 6.974 16 29 2860 0.1924 6.834 17 Best Mean Stall Generation Func-count Penalty Penalty Generations 30 2955 0.1924 6.965 18 31 3050 0.1924 6.723 19 32 3145 0.1924 6.691 20 33 3240 0.1924 6.826 21 34 3335 0.1924 6.42 22 35 3430 0.1924 7.587 23 36 3525 0.1924 6.693 24 37 3620 0.1924 6.599 25 38 3715 0.1924 7.044 26 39 3810 0.1924 7.01 27 40 3905 0.1924 6.904 28 41 4000 0.1924 7.001 29 42 4095 0.1924 7.112 30 43 4190 0.1924 7.257 31 44 4285 0.1924 6.885 32 45 4380 0.1924 7.561 33 46 4475 0.1924 7.402 34 47 4570 0.1924 6.832 35 48 4665 0.1846 6.513 0 49 4760 0.1846 7.388 1 50 4855 0.1846 6.561 2 51 4950 0.1846 7.163 3 52 5045 0.1846 6.261 4 53 5140 0.1846 6.571 5 54 5235 0.1627 7.58 0 55 5330 0.1627 6.964 1 56 5425 0.1627 6.975 2 57 5520 0.1627 7.488 3 58 5615 0.1627 7.395 4 59 5710 0.1627 6.782 5 Best Mean Stall Generation Func-count Penalty Penalty Generations 60 5805 0.1627 6.871 6 61 5900 0.1627 7.882 7 62 5995 0.1627 7.149 8 63 6090 0.1627 7.11 9 64 6185 0.1627 8.138 10 65 6280 0.1627 7.423 11 66 6375 0.1437 6.583 0 67 6470 0.1437 7.542 1 68 6565 0.1437 7.109 2 69 6660 0.1437 7.021 3 70 6755 0.1437 7.376 4 71 6850 0.1437 7.051 5 72 6945 0.1437 6.833 6 73 7040 0.1437 7.347 7 74 7135 0.1437 7.571 8 75 7230 0.1437 6.836 9 76 7325 0.1437 6.689 10 77 7420 0.1437 7.386 11 78 7515 0.1437 7.527 12 79 7610 0.1437 8.611 13 80 7705 0.1437 7.166 14 81 7800 0.1437 7.431 15 82 7895 0.1018 6.76 0 83 7990 0.1018 7.822 1 84 8085 0.1018 7.225 2 85 8180 0.1018 6.675 3 86 8275 0.1018 6.842 4 87 8370 0.1018 7.205 5 88 8465 0.1018 7.067 6 89 8560 0.1018 7.213 7 Best Mean Stall Generation Func-count Penalty Penalty Generations 90 8655 0.1018 7.64 8 91 8750 0.1018 7.24 9 92 8845 0.1018 7.211 10 93 8940 0.1018 7.247 11 94 9035 0.1018 6.683 12 95 9130 0.1018 6.194 13 96 9225 0.1018 6.716 14 97 9320 0.1018 7.644 15 98 9415 0.1018 7.178 16 99 9510 0.1018 6.731 17 100 9605 0.1018 6.795 18 101 9700 0.1018 7.494 19 102 9795 0.1018 7.47 20 103 9890 0.1018 7.36 21 104 9985 0.1018 7.195 22 105 10080 0.1018 6.354 23 106 10175 0.1018 6.793 24 107 10270 0.1018 6.629 25 108 10365 0.1018 7.468 26 109 10460 0.1018 8.36 27 110 10555 0.1018 8.104 28 111 10650 0.1018 7.618 29 112 10745 0.1018 7.087 30 113 10840 0.1018 7.327 31 114 10935 0.1018 6.542 32 115 11030 0.1018 7.579 33 116 11125 0.1018 7.069 34 117 11220 0.1018 7.284 35 118 11315 0.1018 6.885 36 119 11410 0.1018 7.423 37 Best Mean Stall Generation Func-count Penalty Penalty Generations 120 11505 0.1018 7.251 38 121 11600 0.1018 7.141 39 122 11695 0.1018 7.167 40 123 11790 0.1018 7.319 41 124 11885 0.1018 6.718 42 125 11980 0.1018 7.185 43 126 12075 0.1018 7.164 44 127 12170 0.1018 7.154 45 128 12265 0.1018 6.278 46 129 12360 0.1018 6.378 47 130 12455 0.1018 7.179 48 131 12550 0.1018 7.575 49 132 12645 0.1018 7.443 50 ga stopped because the average change in the penalty function value is less than options.FunctionTolerance and the constraint violation is less than options.ConstraintTolerance.
Bvec = 1×57
1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0
<mw-icon class=""></mw-icon>
<mw-icon class=""></mw-icon>
Fval = 0.1018
exitflag = 1
Elapsed time is 0.902223 seconds.
If you were worried that GA might not have found the truly optimal solution, you could force it to run a little longer. But it seems to have converged to a happy place. And it only used less than a second of CPU time, which in my opinion is a finite amount of time.

Categorie

Scopri di più su Problem-Based Optimization Setup in Help Center e File Exchange

Tag

Prodotti

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by