巡回セールスマン問題を解く（２）

　40点ぐらいなら良いけど、80点以上になってくると、かなり難しくなります。200点なんて、絶望的に難しいです（冷静に考えれば (n-1) !　から抽出するのだからしょうがない事なのかもしれない）。集団サイズは1世代あたり点数の2倍として試行錯誤し、そこそこ性能も良くなりました。40点に対して 160世代目ぐらいで安定するけど、1700世代ぐらいに忽然と世代交代する場合もあって難しいです。
　突然変異には、今のところ乱数で min( N / 2 + 1, 20 ) を最大として任意の位置を錯乱させるものと、任意の2点を交換するものをミックスしています。これらが辺組み換えオペレータと相性が良いような気がしてます。前者は局所的な改善に、後者は大局的な改善を促します。
　ＧＡは、一度にたくさんの改善をしようと思って、欲張りすぎると淘汰されてしまいます。なので、ちょっとづつ改善するしかないのですが、80点以上になると改善して欲しい場所に突然変異が適用される確率が低くなるので集団サイズを増やすか世代数を増やすしかなくなります。こういう理由から、2-opt や or-opt を組み合わせるという発想になるのだと思います。
　既に 40 点ぐらいの問題ならば、2-opt や or-opt を併用しなくても良い経路に収束するレベルにあるので、plpgsql 化しても良さそうです。
　今後の課題は、世代交代の収束回数に応じて 2-opt や or-opt を併用して 局所解への収束ステージを設けて、スイッチするなどの工夫を取り入れることです。正直 2-opt や or-opt のコーディングは面倒くさそうなので、このままお茶お濁すかも…(^^;

巡回セールスマン問題を解く

　pgRouting の TSP がお亡くなりになるのは、多分、自明な3点の問題を解く場合に限るだろうという事で、放置する事にしました。しかしサービス・ルーチンとして利用するからには、いつ、お亡くなりにならないように修正されますか？という爆弾を抱えている状態なので、難問ながらも、自前でルーチンの作成を試みることにしました。使い物になるレベルになるか？仮に使えるようになったら公開するか？は別問題で、今は考えないことにします。
　TSPの解法として、kd-tree, TS,SA,GA等いろいろありますが、あまり深く考えないでもコーディングできそうなGAを選択する事にしました。参考にした本は「組合せ最適化アルゴリズムの最新手法―基礎から工学応用まで」です。最初はSimEを実装しようと読んでいたのですが、これは、どうも 2-opt, or-opt の事を書いてあるような気がするし、わからないので、やめました。
　GAでTSPを実装する上での問題は、

• どのようなアルゴリズムで子供を作成するか？
• 集団サイズは、どのぐらいにするか？
• 突然変異をどのように扱うか？

です。
　子供を作成するアルゴリズムは、辺組み換えオペレータ[WSF89]にしました。本を参考に実装してみたけれど、実際には孤立する辺や点が出現し、これらを考慮しなければなりませんでした。しかし、解説にあるように両親の良さをうまく受け継いでくれるようで、いい感じです。
　集団サイズは、とりあえず４０としました。
　突然変異も試行錯誤しました。2-opt や or-opt を使わないと GA だけでは、なかなか良い結果が得られないという解説が多いですが、結構いい線いくようになりました。下手な鉄砲も数撃ちゃ当たるでしょうか？
　はまったのは、辺組み換えオペレータでは同一の親が発生しやすく、同じ親を除去する部分でした。

1. 経路長でソートして配列を比較してましたが、状況が改善されません
2. 0番目に特定の点が来るようにローテーションをかけてから比較するようにしましたが、だめ
3. 1番目の点と最後の点を比較して、必ず若い番号が1番目に来るように順序を反転

以上の操作で、やっと重複を取り除く事ができました。
　しかし、現在40点でテストを試みてますが、安定するまでに600世代から2400世代繰り返しが必要です。まだまだ工夫の余地があり、結構、奥が深いのねん…。

位相の基礎本

　今回は、ちょっと毛色の変わった本を紹介してみようと思います。大学の数学では、線形代数と微分積分（ε-δ法）をやって、複素平面あたりをやるのでしょうか？で、数学専門の課程に入ると代数（群論・環論）、幾何（トポロジー・ホモロジー）、解析（微積分：リーマン・ルベーグ・確率論）を扱うのかな？
　連続の概念など、位相の概念を理解しないと、しんどいです。そんな中で、一番理解し易く解説してあると思ったのが「意味がわかる位相空間論」です。しかし、本書を必要とする人は少数だろうなぁ。

boost::multi_array に algorithm 適応

　前回の記事で、がっくしきたが、一応解決方法を提示

void multi_array_test( int x, int y ) {
  boost::multi_array<int,2> ma( boost::extents[x][y] );
  for( int i = 0; i < x; ++i ) {
    for( int j = 0; j < y; ++j ) {
      ma[i][j] = i + j;
    }
    std::random_shuffle( &ma[i][0], &ma[i][y-1] + 1 );
  }
  for( int i = 0; i < x; ++i ) {
    for( int j = 0; j < y; ++j ) {
      std::cout << ma[i][j] << ",";
    }
    std::cout << std::endl;
  }
}

&ma[i][y-1] は、配列の末端のアドレスにあたるわけだが、これに +1 をしてやれば、&ma[i][y] に等しいアドレス、すなわち end() に相当するアドレスが得られる。
　+1 に違和感を持つ人もいるかもしれないので補足すると、型が int のポインタなので、+1 する事で、sizeof(int*)sizeof(int) × 1 が加算される。

追記: iterator 使えるじゃんかよ… orz
追記(2009/03/14): boost_1_38_0 時点での multi_array は、１次元配列から自前で計算した方が速いようだ。

C++ 2次元配列の確保

　ふと、動的に2次元配列を構築したいと思い。あれれ？どんな構文だったっけかな？と、検索してみたが、意外に情報源が無い。見つかったのは、動的にポインタの1次元配列を構築し、for 文で各列に対して2次元目の配列を構築するという方法。これは、ちょっとどうなの？って内容だ。
　2次元目以後の長さが決まっているならば、

  int len = 10;
  int (*tes)[4] = new int [len][4];

のように一発で確保できるのだが、そうでなければ1次元配列を確保して、自分でマッピングするより無さそう。新しい規格だと、この辺も改善されていたような…ないような…。不勉強で、よくわからない（そんな時間もない）。
　で、boost::multi_array で試してみたら、これで十分じゃんという結論に…。

#include <iostream>
#include <boost/multi_array.hpp>

void multi_array_test( int x, int y ) {
  boost::multi_array<int,2> ma( boost::extents[x][y] );
  for( int i = 0; i < x; ++i ) {
    for( int j = 0; j < y; ++j ) {
      ma[i][j] = i + j;
    }
  }
  for( int i = 0; i < x; ++i ) {
    for( int j = 0; j < y; ++j ) {
      std::cout << ma[i][j] << ",";
    }
    std::cout << std::endl;
  }
}

int main() {
  int x = 10;
  int (*tes)[4] = new int [x][4];
  for( int i = 0; i < x; ++i ) {
    for( int j = 0; j < 4; ++j ) {
      tes[i][j] = i + j;
    }
  }
  for( int i = 0; i < x; ++i ) {
    for( int j = 0; j < 4; ++j ) {
      std::cout << tes[i][j] << ",";
    }
    std::cout << std::endl;
  }
  delete [] tes;
  std::cout << "---------------" << std::endl;
  multi_array_test( 3, 4 );
  std::cout << "---------------" << std::endl;
  multi_array_test( 4, 6 );
  return 0;
}

追記：
　しかし、algorithm が使えない… orz

  std::random_shuffle( &ma[i][0], &ma[i][y] );

とやると、Assertion failed: size_type(idx - index_base[0]) < extents[0]
ちょっと～～～～～～～
追記(2009/03/14): boost_1_38_0 時点では、multi_array のパフォーマンスは良いとは言えない

ユートピア以前の歴史

　何気に怪しいタイトル(^^;。ふと、ＳＦの世界でられるような人間が働かなくて、自己研鑽に勤しむユートピアのような世界と、それ以前の世界との間には、もの凄いギャップがありそうで、その間の文化は、どのようになるのだろうか？と疑問に思いました。
　人間が働かなくて良いという事情は無いのに、生産性が上がって常時に全ての人が働くべき職も無い状況。こんな世界では、どんな文化が構築されるのでしょうか？
　今の状況は、農業・工業・サービス業のうち工業だけが突出して生産性が上がっていて、簡単な仕事は人件費の安い所へ流れているという構図だと感じます。そうすると、スポットライトを浴びるのは農業！
　ユートピアを構築するには、農業の生産性を上げて流通を革命する事が課題なんでしょうか？などと空想しています。

　うおーっ、息子にキーボードいじられてやばい状況・・・げあｊｆ

いろいろ

　人気コンテンツは、Android SDK のインストール方法で、当の本人は、アンドロイドＳＤＫで遊ぶ暇もなく放置プレーで、なんだかガックリくる。ハウツーもんを書けばアクセスも上がるかもしれないけど、趣旨が異なるので、なるべく書かないようにする。
　ここ数日は暖かくて道路がグシャグシャ…歩くのが怖い。それよりも温暖化がマジ怖いです。
　Visual Studio 2005 は、ハングしまくりの落ちまくりで、同時コンパイル数を１にしますた。それでも1日に4回は強制電源オフをして、chkdsk /F あまりにひどいので chkdsk /R で仕事にならーーーーん。Windows Vista は、Micsosoft Access 1.0 に次いで２番目にひどい出来ではないかと思います。はよ Windows7にしてくれ。
　車なし生活は、ちょっと出たいという時には不便だなと感じる事もあるけど、４歳の息子が歩く機会が増えて、これはこれで良かったと思います。
　後は愚痴っぽくなりそうなんで、この辺でやめときます。

boost::xpressive サンプル

　vc8 から vc9 へ移行しようと思うと、atlrx.h が見つからない。という訳で正規表現の関係を書き直すはめに…。ちなみに、afxisapi.h が無くなっていて、オープンソース化した atlisapi.h を使えというひどい対応により、移行は実現できないでいる。そんなこんなで、boost::xpressive なのだ…。

#include <iostream>
#include <string>
#include <boost/xpressive/xpressive.hpp>

bool separate_word(
 const char* parse,      //!< [in] 節の正規表現文字列
 const std::string& src, //!< [in] 文
 std::string& before,    //!< [out] 節の前文
 std::string& sep,       //!< [out] 節
 std::string& after      //!< [out] 節の後文
) {
 boost::xpressive::sregex rex = boost::xpressive::sregex::compile( parse );
 boost::xpressive::smatch what;
 if( !boost::xpressive::regex_search( src, what, rex, boost::xpressive::regex_constants::match_any ) ) return false;
 before = src.substr( 0, what.position(0) );
 after  = src.substr( what.position(0) + what.length(0) );
 sep    = what[0];
 return true;
}

int main(void) {

 std::string src = "select() d,e,f from (select a, b, c from hiho (Where) anywheresql=5 order by a ) where moge=3";
 const char* parse[] = {
   "\\b(?i:order +by)\\b",
   "[^\\ \\(\\)\\,]+",
   "\\b(?i:where)\\b"
 };

 for( int i = 0; i < 3; ++i ) {
   std::string bef, aft, sep;
   separate_word( parse[i], src, bef, sep, aft );
   std::cout << ">>>>" << std::endl;
   std::cout << bef << std::endl << sep << std::endl << aft << std::endl;
 }
 std::cout << "===============" << std::endl;
 boost::xpressive::sregex reg = boost::xpressive::sregex::compile( " +" );
 boost::xpressive::sregex_token_iterator cur( src.begin(), src.end(), reg, -1 );
 boost::xpressive::sregex_token_iterator end;
 while( cur != end ) {
   std::cout << *cur << std::endl;
   ++cur;
 }
 std::cout << "---------------" << std::endl;

 return 0;
}

zlib-1.2.3 備忘録

　いい加減 VC8 から VC9 へプロジェクトを移行したいと思って、zlib 系でコンパイルして、
LNK2019 _inflateEnd というようなエラーで、しばらく悩んだ…。コンパイルしたのは、contrib/vstudio/vc8 の方である。

　zconf.h を include する前に

#define ZLIB_WINAPI 1

してやればよい。

追記：
/projects/visualc6 の方を使ってコンパイルしても良い。アセンブラでエラーになるが、[] の前に dword ptr を修飾してやればコンパイルは通る。この場合
zconf.h を include する前に

#define ZLIB_DLL

してやればよい（ZLIB_WINAPI）しない事。

地球温暖化だろ・・・コレ

　1月下旬にさしかかろうとしているのに、札幌で＋7度の気温で、道路中が溶けてベショベショ…。そして、春の嵐がやってきた…。これ、3月下旬の天気だろ？積雪量も極端に少なくて、信じられない状況。これは異常だ…と、隣家の人と話していたら、北海道新聞にも「冬異変」との見出しで、道内の平均気温と積雪量の平年比が出ていた。その表によると、およそ＋２度ぐらいは高い。差が小さいのは室蘭の＋0.9度、大きいのは北見の+3.0度、気温は軒並み上がっているが、面白いことに積雪量は＋になっているところもあり、温暖化！＝積雪量減少のようです。
　

glutといえば

　windows環境で、glut を使おうと思って、一生懸命コンパイルしても、まともに動作しません。で、探したら freeglut というのがあって、こちらを使うと良いです。
　何気に思い出したので備忘録としてポストしますた。

shortest_path2

　pgRouting 1.03 ベースに最短経路探査ルーチンを追加したので、一応、貼っておく。

ふんがーー

　使おうと思っていたやつの別のルーチンにもバグを見つけてしまった。そこを直しても、お亡くなりになるパターンがあるようで、結局、全部、俺が書くんかい～～っ！と、一人突っ込みを入れて笑うしかない状況。仕事多すぎて、こなせませんわ。こんなペースで仕事してたら、心臓麻痺で過労死するわ・・・。今日は、この辺でやめとこ・・・。精神的に持ちません。

ubuntu8.10+4965agn

　自宅のubuntuは8.10に上げてしまったが、無線LANが動作しなくなるので、古いカーネルを残しておりました。しかし、最近NVIDIAのドライバが更新されるに伴って、古いカーネルでグラフィック・ドライバが機能しなくなったため、この辺を突っ込んで調査する事に・・・。
　で、見つけたのが、この記事。うちの環境では、WICDを入れてるので、状況が少し異なっていると思うけど、まあ、やってみようと　make install まで実行できたけど、make unload が、どうにも通らない。

root@werdna:/usr/src/compat-wireless-2009-01-11# make unload
Unloading mac80211...
FATAL: Module mac80211 is in use.
Unloading cfg80211...
FATAL: Module cfg80211 is in use.
make: *** [unload] エラー 1
root@werdna:/usr/src/compat-wireless-2009-01-11# make load
Unloading mac80211...
FATAL: Module mac80211 is in use.
Unloading cfg80211...
FATAL: Module cfg80211 is in use.
make: *** [unload] エラー 1

　いろいろ検索してみた結果、cfg80211 というのは blacklist に載せた方が良いらしいので、/etc/modprobe.d/blacklist に次の1行を追加した。

# causes no end of confusion by creating unexpected network interfaces
blacklist eth1394  # ここは元からあり、追加したのは、次の1行
blacklist cfg80211

あれ？ make unload, make load しなくても無線LANが使えるようになっているんですけど？？？もしかしたら、blacklist cfg80211 だけでＯＫだったのかな？

2009/01/16 追記
blacklist cfg80211 は、全く機能していないようだ。繋がる時と繋がらない時がある。結局のところ、よくわからない。

2009/01/26 追記
synaptic manager より、linux-backports-modules-intrepid をインストールしたら、だいぶ改善された

合衆国再生、やっと読んだ

　「合衆国再生―大いなる希望を抱いて」をやっと読みました。

エクセレント！

オバマ大統領、直球勝負です。ＩＴも理解しているし、ここ最近、私が感じたような事も既に考えられてありました。銃禁止のタブーにも触れており、気になる中絶問題も良識的にとらえてます。グローバルな世界では、世界が協調しないと問題が解決しない点を指摘している事が素晴らしい。ここまで凄いと逆に暗殺されてしまうのではないか？という危惧までいだいてしまいます。そうならない事を願ってやみません。

　それにひきかえ、日本の首相は自分の面子にこだわっている状況、私は、渡辺 喜美議員の行動にブログからエールを送りたい。対投資効果として単なる”ばら撒き”は、何の意味も無い。

OKかたづいた

　結局、仕様をよく読まずにコーディングしてハマっていた…という事だった。
palloc は現メモリコンテキストに、SPI_palloc は上位メモリコンテキストに、でもSPI_pfree は、互換性のためだけに存在して、pfree でメモリは解放。名前の付け方、わかんねーよ…と他人のせいにしてみる…。ちくしょー(;_;)。
　今まで、フリーしたメモリ領域に無断でアクセスしていたため、他のプロセスやスレッドに再利用されている場合に限りセグメンテーション・フォルトを起こしていた。という事のようだ。ようやく安定稼働して、これで公開しても大丈夫だろう。バグ直した通知しなきゃ…。

原因がわかった

　かたづいてなかったの続き、ようやく原因がわかった。postgresql の SPI_finish の呼び出し時期が早かったようだ。しかし、まだ釈然としない。SPI_finish の説明では、呼び出し元のメモリコンテキストにスイッチし、その呼び出し元のメモリコンテキスト内では、palloc で確保されたメモリは有効であると記述されているが、その状況を待たずして pfree されてしまっていたという事のようだ。
　一時的に利用するだけなので自動変数で良いと推察される所にわざわざ palloc と pfree を利用する公式のサンプルコードにしても、その意図がわからなくて不安になります。
　今渡こそかたづくだろ…。

かたづいてなかった

　かたづいたはずのサーバ・サイド・プログラミングですが、かたづいてませんでした。Segmentation Fault で落ちる場合がありました。また、バグも発見（これは修正した）。で、この Segmentation Fault を追ってみたけど、なんで、こんなところで落ちるのか、さっぱりわからない。スタック破壊というわけでもなさそうで、スレッドやプロセス絡みだと、えーそこまで追わなきゃダメ？って感じで、げんなりする。
　元のやつにも、問題の箇所に怪しげなコードが提示されている。これは、ちょっとキツイだろ・・・。エンドレス・オブ・Yak Shaving?な予感・・・しんどいなぁ、もう〜。
　同時進行で明日はPマーク審査だ(-_-)

USJの再入場禁止

　「USJ、7日から再入場禁止」
　実家へ帰省したついでに、年末にＵＳＪへ行って不満たらたらだったので書いておく。サービスにおいてもイノベーションを起こさないと、この先、生き残る事はできない。ＵＳＪはダメダメだ。
　まず、ウェブでチケットを購入して出かけたにもかかわらず、入場するのに１時間も並ばされるハメに陥った。飛行機のチケットもＱＲコードでチケットレスサービスをする時代にだ！偽チケットが怖ければ、日付とシリアルとＣＲＣをセットにして署名すれば良いだけの話。ＩＴに疎いはずの嫁さんまで、このサービスのなってなさには憤慨していた。
　次に食事の価格、いくらプレミアム価格と言っても物には限度がある。私の前に並んでいた2人組が、マクドナルドで提供しているものと変わらない食事に4800円の会計をしていた。目玉が飛び出るサプライズだ。この値段だと北海道で回転寿司に「大トロ・中トロ・ウニ」等の豪華一品をチョイスして食っても、お釣りが出る（いいネタを食べても2人で3500円までは行かない）。
　ＵＳＪに行ったのは2回目だが、2回目に行った時は激混みでアトラクション２つしか回れなかった。並ばなくても優先的に搭乗できるチケットが買えなかったのも大きい。優先搭乗チケットは発行し過ぎだろ。地元で空いている時期に入場できるという条件でなければ、ＵＳＪへは2度と行かないだろう。
　再入場の禁止を決定する前に、やっておく事があるだろ？エンターテイメントだけでは駄目だ。

経営の未来

　ブログをやって良かったと思ったのが、「経営の未来」という本を見つけられた事。お勧め本のリコメンデーションでゲットしました。（年末に記事書いとけよ・・・と思った方・・・すみません）
　変化の激しい現在に企業が対応していくための経営システムを構築する、という難題を突きつけた本です。システム屋さんが、「社会変化に対してＡＩのように勝手に対応する経営システムを構築せよ」というシステムを請け負ったら頭を抱えると思います。本書に解決策が書いてある訳ではありませんが、3社の新しい経営システムの例と、新しい経営システムを構築する（経営のイノベーション）ためのヒントが書いてあります。例に挙げられているのは、おなじみグーグルに、アウトドア派なら馴染みの深いゴアテックスの会社と、アメリカのホールフーズというスーパーです。
　経営に関わる人には読んで欲しい本です。

世界不況を理解するための本

　実家に帰って薦められた本の中で、面白かったのが「強欲資本主義-ウォール街の自爆」で、経済も勉強しないと不利益を被ると実感させられました。この本に書かれているのは、著者が内側から見た「お前の利益は俺のもの、俺の損失はお前のもの」という投資プレーヤの実態。ファンドもどきに成り下がった日本の銀行と、それを後押しした日本の政策について考えさせられます。
　これに比べれば全部を書いていないだろうけど面白かったのが「ソロスは警告する」で、こちらは先の本に出てくるプレーヤと違ってハイリスク・ハイリターンを地でいく感じのプレーヤ。3章あたりの再帰性理論は何を書いてあるのかさっぱり要領を得ず、投資した結果を受けて世の中が波紋のように動くというような事だろうと勝手に解釈して読み飛ばしたが、基本的な世界不況の原因については深い考察がされているように思います。
　そして前ＦＲＢ議長であるグリーンスパンさんの書いた「波乱の時代-特別版―サブプライム問題を語る」は、外せないところでしょうか？サブプライムを発端とする複雑な金融商品を取り巻く環境に対して、各銀行等が、もっとリスク対策をしていなかったのは予想外で市場原理に沿って危険な商品は淘汰されるはずだったとしています。また、サブプライムの問題が無くても、別の問題が起こって、同じような状況を作り出していただろうという指摘が印象的でした。

今年もよろしく

　新年、あけましておめでとうございます。ようやくネットのある生活に復帰しました。未読が予想していたよりも少なくてよかった・・・。年末から正月にかけては、主に現在の世界不況に関する本を読みました。ともかく、今年もよろしくお願いします！