Nichtlineare Optimierung in N Dimensionen

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    Unsere Datenschutzerklärung wurde aktualisiert. Mit der Nutzung unseres Forums akzeptierst Du unsere Datenschutzerklärung. Du bestätigst zudem, dass Du mindestens 16 Jahre alt bist.

    • Abt. Nichtlineare Optimierung in N Dimensionen
      ==============================
      Das Verfahren von Nelder & Mead :!: ist eine relativ einfache, daher robuste Suche nach Minima bzw. Maxima auf einer zwei- oder mehrdimensionalen Fehler-, Kosten- oder Gewinnfunktion (Im Gegensatz zu anderen Verfahren kommt es ohne partielle Ableitungen aus).

      Wie alle solche Verfahren besteht auch hier die Gefahr, in bloß lokalen Optimalpunkten hängenzubleiben. Daher sollte man stets mehrere Duchläufe mit geänderten Anfangs-Eckpunkten des "wandernden Dreiecks" (2D) bzw. wandernden Tetraeders (3D) bzw. Simplexes (>3D) durchspielen.

      Der Algorithmus selbst stammt aus dem Jahre 1965 und wurde aus HP-BASIC nach XProfan 11 transkribiert. Erste Versuche verliefen bei mir ohne große Fehler. Hier meine Umsetzung nach XProfan 11 - aber wie immer ohne jede Gewähr:

      Quellcode

      1. WindowTitle "Nelder-Mead Downhillsimplex zur Optimierung auf n-dimensional-nichtlinearen Funktionen"
      2. ' (Tr) 2012-07 übersetzt aus HP-Basic nach XProfan 11.2a by P. Specht, Wien
      3. ' Umsetzung ohne jegliche Gewähr!
      4. ' Nelder Mead-Methode für n Dimensionen
      5. '
      6. REM Rechtsvermerke der Originalvorlage:
      7. REM Copyright 1987
      8. REM John H. Mathews
      9. REM Dept. of Mathematics
      10. REM California State University, Fullerton
      11. REM Nelder-Mead Method for N-Dimensions
      12. Window 0,0 - %maxx,%maxy-44
      13. CLS:Font 2
      14. Declare N&,K&,J&,FUN$,L$,R$,A$,ANS$
      15. Declare Epsilon!,x!,y!,z!,u!,v!,w!,F!,S!,Norm!,YR!,YE!,YC!
      16. Declare LO&,HO&,HI&,LI&,Max&,Min&,Count&
      17. Goto "L100"
      18. Proc S10 ' FUNCTION
      19. X! = P![1] : Y! = P![2] : Z! = P![3]
      20. U! = P![4] : V! = P![5] : W!=P![6]
      21. '====================================
      22. F! = X!*X! - 4*X! + Y!*Y! - Y! - X!*Y!
      23. '====================================
      24. 'Weitere Testfunktionen:
      25. ' Rosenbrock-„Bananenfunktion“
      26. 'f(x,y)=(1-x)^2+100*(y-x^2)^2
      27. 'min bei 1,1 mit f(x,y)=0
      28. ' Himmelblau-Funktion
      29. 'f(x,y)=(x^2+y-11)^2+(x+y^2-7)^2
      30. 'max bei x=-0.270845, y=-0.923039 mit f(x,y)=181.617
      31. '4*min: f(3.0,2.0)=0.0 f(-2.8051118,3.131312)=0.0
      32. 'f(-3.779310,-3.283186)=0.0 f(3.584428, -1.848126)=0.0
      33. '====================================
      34. EndProc
      35. ' Proc PRINT
      36. Proc S20
      37. N&=2
      38. FUN$ ="X*X - 4*X + Y*Y - Y - X*Y"
      39. C$[1] = "[X' : C$[2] = ",Y" : C$[3] = ",Z"
      40. C$[4] = ",U" : C$[5] = ",V" : C$[6] = ",W,"
      41. L$ =" F" : R$ ="] = "
      42. Print L$;C$[1];
      43. WhileLoop 2,N&: K&=&Loop
      44. Print C$[K&];
      45. EndWhile
      46. Print R$;FUN$
      47. Return
      48. EndProc
      49. '{ Hauptteil PROGRAM NELDER MEAD
      50. L100:
      51. Epsilon! = +1*10^-5
      52. Declare C$[6],C![6],E![6],M![6],P![6],R![6],V![6,6],Y![6],Z![6]
      53. L120:
      54. REM SUBROUTINE INPUTS
      55. S1000
      56. REM SUBROUTINE NELDER MEAD
      57. Gosub "S200"
      58. REM SUBROUTINE OUTPUT
      59. S2000
      60. Print "\n WANT TO TRY NEW STARTING VERTICES ? ";
      61. Input ANS$
      62. Case (ANS$ = "Y") Or (ANS$ = "y") : Goto "L120"
      63. Goto "L9999"
      64. '}
      65. S200:
      66. REM SUBROUTINE NELDER MEAD
      67. MIN&=10
      68. MAX&=200
      69. COUNT&=0
      70. REM Order the vertices.
      71. LO&=0 : HI& =0
      72. WhileLoop N& : J&=&Loop
      73. case Y![J&] < Y![LO&] : LO&=J&
      74. case Y![J&] > Y![HI&] : HI&=J&
      75. EndWhile
      76. LI&=HI& : HO&=LO&
      77. WhileLoop 0,n&:J&=&Loop
      78. case (J& <> LO&) AND (Y![J&] < Y![LI&]) : LI&=J&
      79. case (J& <> HI&) AND (Y![J&] > Y![HO&]): HO&=J&
      80. EndWhile
      81. ' =======================================================================
      82. While (Y![HI&] > (Y![LO&] + EPSILON!)) And ( (COUNT&<MAX&) Or (COUNT&<MIN&) )
      83. REM The main loop
      84. REM Form new vertices M and R
      85. WhileLoop N&:K&=&Loop
      86. S!=0
      87. WhileLoop 0,N& : J& = &Loop
      88. S!=S!+V![J&,K&]
      89. EndWhile
      90. M![K&]=(S!-V![HI&,K&]) / N&
      91. EndWhile
      92. WhileLoop N&: K&=&Loop
      93. R![K&]=2*M![K&]-V![HI&,K&]
      94. P![K&]=R![K&]
      95. EndWhile
      96. REM SUBROUTINE FUNCTION
      97. S10
      98. YR!=F!
      99. REM Improve the simplex.
      100. If YR! < Y![HO&] : Goto "L375" : Else : Goto "L525" : EndIf
      101. L375:
      102. IF Y![LI&] < YR! : Goto "L380" : Else : Goto "L410" : EndIf
      103. L380:
      104. REM Replace a vertex
      105. WhileLoop N&:K&=&Loop
      106. V![HI&,K&]=R![K&]
      107. EndWhile
      108. Y![HI&]=YR!
      109. Goto "L515"
      110. L410:
      111. REM Construct vertex E.
      112. WhileLoop N&: K&=&Loop
      113. E![K&]=2*R![K&]-M![K&]
      114. P![K&]=E![K&]
      115. EndWhile
      116. REM DO SUBROUTINE FUNCTION
      117. S10
      118. YE!=F!
      119. IF YE! < Y![LI&] : GOTO "L455" : ELSE : GOTO "L480" : ENDIF
      120. L455:
      121. WhileLoop N&: K&=&Loop
      122. V![HI&,K&]=E![K&]
      123. EndWhile
      124. Y![HI&]=YE!
      125. Goto "L510"
      126. REM ELSE
      127. L480:
      128. REM Replace a vertex.
      129. WhileLoop N&: K&=&Loop
      130. V![HI&,K&]=R![K&]
      131. EndWhile
      132. Y![HI&]=YR!
      133. L510:
      134. REM ENDIF
      135. L515:
      136. REM ENDIF
      137. Goto "L700"
      138. L525:
      139. If YR! < Y![HI&] : Goto "L535" : Else : Goto "L560" : EndIf
      140. L535:
      141. REM Replace a vertex
      142. WhileLoop N& : K&=&Loop
      143. V![HI&,K&]=R![K&]
      144. EndWhile
      145. Y![HI&]=YR!
      146. L560:
      147. REM CONTINUE
      148. REM Construct vertex C
      149. WhileLoop N& : K& = &Loop
      150. C![K&]=(V![HI&,K&]+M![K&])/2
      151. P![K&]=C![K&]
      152. EndWhile
      153. S10
      154. ' REM SUBROUTINE FUNCTION
      155. YC!=F!
      156. If YC! < Y![HI&] : Goto "L605" : Else : Goto "L630" : EndIf
      157. L605:
      158. WhileLoop N&: K&=&Loop
      159. V![HI&,K&]=C![K&]
      160. EndWhile
      161. Y![HI&]=YC!
      162. Goto "L695"
      163. L630:
      164. REM ELSE
      165. REM Shrink the simplex
      166. WhileLoop 0,N& : J&=&Loop
      167. If J& <> LO& : Goto "L650" : Else : Goto "L685" : EndIf
      168. L650:
      169. WhileLoop N& : K& = &Loop
      170. V![J&,K&]=(V![J&,K&]+V![LO&,K&])/2
      171. Z![K&]=V![J&,K&]
      172. P![K&] = Z![K&]
      173. EndWhile
      174. S10
      175. ' REM SUBROUTINE FUNCTION
      176. Y![J&]=F!
      177. L685:
      178. REM CONTINUE
      179. EndWhile
      180. L695:
      181. REM ENDIF
      182. L700:
      183. REM ENDIF
      184. COUNT&=COUNT&+1
      185. REM Order the vertices.
      186. LO&=0
      187. HI&=0
      188. WhileLoop N& : J&=&Loop
      189. case Y![J&] < Y![LO&] : LO&=J&
      190. case Y![J&] > Y![HI&] : HI& =J&
      191. EndWhile
      192. LI&=HI&
      193. HO&=LO&
      194. WhileLoop 0,N&:J&=&Loop
      195. case (J& <> LO&) AND (Y![J&] < Y![LI&]) : LI&=J&
      196. case (J& <> HI&) AND (Y![J&] > Y![HO&]): HO&=J&
      197. EndWhile
      198. WEND
      199. ' =======================================================================
      200. REM Determine the size of the simplex
      201. NORM!=0
      202. WhileLoop 0,N&:J&=&Loop
      203. S!=0
      204. WhileLoop N&: K&=&Loop
      205. S!=S! + ( V![LO&,K&] - V![J&,K&] ) * ( V![LO&,K&] - V![J&,K&] )
      206. EndWhile
      207. case S! > NORM! : NORM!=S!
      208. EndWhile
      209. NORM!=SQRT(NORM!)
      210. Return
      211. REM SUBROUTINE INPUTS
      212. Proc S1000
      213. CLS
      214. Print " THE NELDER-MEAD SIMPLEX METHOD OR `POLYTOPE METHOD` IS"
      215. Print "\n USED FOR FINDING THE MINIMUM OF THE FUNCTION F(V)"
      216. Print "\n FOR CONVENIENCE, THE FUNCTION F(V) CAN BE EXPRESSED USING"
      217. Print "\n THE VARIABLES X = v , Y = v , Z = v , U = v , V = v , W = v ."
      218. Print " 1 2 3 4 5 6 "
      219. Print
      220. ' REM DO SUBROUTINE PRINT FUNCTION
      221. S20
      222. Print "\n YOU MUST SUPPLY",int(N&+1)," LINEARLY INDEPENDENT"
      223. Print
      224. If N& = 2 : Goto "L1160" : Else : Goto "L1190" : EndIf
      225. L1160:
      226. Print " STARTING POINTS V = ( v , v ) FOR J=0,1,3"
      227. Print " J J,1 J,2"
      228. Goto "L1280"
      229. L1190:
      230. REM ELSE
      231. If N& = 3 : Goto "L1210" : Else : Goto "L1240" : EndIf
      232. L1210:
      233. Print " STARTING POINTS V = (v,v,v) FOR J=0,1,3,4"
      234. Print " J J,1 J,2 J,3"
      235. Goto "L1280"
      236. L1240:
      237. REM ELSE
      238. PRINT " STARTING POINTS V = (v,v,...,v) FOR J=0,1,...,N"
      239. PRINT " J J,1 J,2 J,N"
      240. PRINT " WHERE N =",N&
      241. L1280:
      242. REM ENDIF
      243. WhileLoop 0,N& : J&=&Loop
      244. PRINT
      245. PRINT " GIVE COORDINATES OF POINT V"
      246. PRINT " ",J&
      247. WhileLoop N& : K&=&Loop
      248. PRINT " V(";J&;",";K&;") = ";
      249. INPUT A$
      250. V![J&,K&]=val(A$)
      251. Z![K&]=V![J&,K&]
      252. EndWhile
      253. WhileLoop N& : K&=&Loop
      254. P![K&] = Z![K&]
      255. EndWhile
      256. ' REM DO SUBROUTINE FUNCTION
      257. S10
      258. Y![J&]=F!
      259. EndWhile ' NEXT J&
      260. Return
      261. EndProc
      262. ' SUBROUTINE OUTPUT
      263. Proc S2000
      264. CLS
      265. Print
      266. Print " THE NELDER-MEAD METHOD WAS USED TO FIND THE MINIMUM OF THE FUNCTION"
      267. Print
      268. ' REM DO SUBROUTINE PRINT FUNCTION
      269. S20
      270. Print
      271. Print " IT TOOK ";COUNT&;" ITERATIONS TO FIND AN APPROXIMATION FOR"
      272. Print
      273. IF N& = 2 : Goto "L2100" : Else : Goto "L2130" : EndIf
      274. L2100:
      275. Print " THE COORDINATES OF THE LOCAL MINIMUM P = (p ,p )"
      276. Print " 1 2"
      277. Goto "L2220"
      278. L2130:
      279. REM ELSE
      280. If N& = 3 : Goto "L2150" : Else : Goto "L2180" : EndIf
      281. L2150:
      282. Print " THE COORDINATES OF THE LOCAL MINIMUM P = (p ,p ,p )"
      283. Print " 1 2 3"
      284. Goto "L2220"
      285. L2180:
      286. REM ELSE
      287. Print " THE COORDINATES OF THE LOCAL MINIMUM P = (p ,p ,...,p )"
      288. Print " 1 2 N"
      289. Print " WHERE N = ";N&
      290. L2220:
      291. REM ENDIF
      292. WhileLoop N& : K&=&Loop
      293. Print "P(";K&;") = ";V![LO&,K&]
      294. EndWhile
      295. Print "\n THE MAXIMUM DISTANCE TO THE OTHER VERTICES OF THE SIMPLEX IS"
      296. Print "\n DP = ";Norm!
      297. Print "\n THE FUNCTION VALUE AT THE MINIMUM POINT IS"
      298. Print "\n F(P) = ";Y![LO&]
      299. Print "\n DF = ";Y![HI&]-Y![LO&];" IS AN ESTIMATE FOR THE ACCURACY."
      300. Return
      301. EndProc
      302. L9999:
      303. End
      Alles anzeigen

      P.S.: Wie man auch entartende Fälle automatisch beherrschen könnte, findet sich im entsprechenden Wikipedia-Artikel sehr gut beschrieben.
      Win7-64HomPremSP1,XProfan11.2a,XPIA,JWasm,xpse,IntelCoreQuad2.5GHz/4GB/je1TB HD intern:esataBay:USB3